[백준] 1713. 후보 추천하기

문제 링크

[백준] 1713. 후보 추천하기

풀이 과정

배열 인덱스 순회를 위해 for...in 구문 사용하면 안되는 이유를 찾아봤습니다.

// for (let i in arr) {
//     let num = arr[i];
for (let i = 0; i < K; i++) {
    let num = arr[i];

처음 코드를 작성할 때, 위 주석과 같이 for…in 구문을 사용해서 배열의 인덱스를 순회했습니다. 하지만, 위 설명처럼 순회 순서가 보장되지 않았기에 계속 틀렸습니다.

Map을 사용해 학생의 사진이 사진틀에 게시되어 있는지 유무를 판단했습니다.

if (candidates.has(num)) {
    candidates.get(num)[0]++;
}

학생 번호 num 이 Map 에 있다면, 해당 학생의 사진이 사진틀에 게시되어 있는 것이므로, 해당 학생의 추천수만 증가시킵니다.

else {
    if (candidates.size === N) {
        let min = null;

        for ([key, value] of candidates.entries()) {
            if (!min) {
                min = [key, value];
                continue;
            }

            const [minCnt, minTime] = min[1];
            const [nowCnt, nowTime] = value;

            if (nowCnt < minCnt || (nowCnt === minCnt && nowTime < minTime)) {
                min = [key, value];
            }
        }

        candidates.delete(min[0]);
    }

    candidates.set(num, [1, i]);
}

학생 번호 num 이 Map 에 없다면, 해당 학생을 사진틀에 추가해야 합니다. 그 과정에서 사진틀이 가득 찬 경우와, 그렇지 않은 경우로 나눌 수 있습니다.

• 사진틀이 가득 찬 경우엔, 삭제할 학생을 골라야합니다. 문제에서 주어진 규칙에 따라 삭제될 학생을 고른 뒤 해당 학생의 사진을 제거한 후, 해당 학생을 추가합니다.
• 사진틀 자리가 남았으므로, 추가만 해줍니다.

코드

const fs = require("fs");
const stdin = (
    process.platform === "linux"
        ? fs.readFileSync("/dev/stdin")
        : `3
14
2 1 4 3 5 6 2 7 2 100 100 54 54 50`
)
    .toString()
    .trim()
    .split("\n");
const input = (() => {
    let line = 0;
    return () => stdin[line++];
})();

const N = +input();
const K = +input();
const arr = input().split(" ").map(Number);
const candidates = new Map();

for (let i = 0; i < K; i++) {
    let num = arr[i];

    if (candidates.has(num)) {
        candidates.get(num)[0]++;
    } else {
        if (candidates.size === N) {
            let min = null;

            for ([key, value] of candidates.entries()) {
                if (!min) {
                    min = [key, value];
                    continue;
                }

                const [minCnt, minTime] = min[1];
                const [nowCnt, nowTime] = value;

                if (nowCnt < minCnt || (nowCnt === minCnt && nowTime < minTime)) {
                    min = [key, value];
                }
            }

            candidates.delete(min[0]);
        }

        candidates.set(num, [1, i]);
    }
}

let answer = "";
[...candidates.keys()].sort((a, b) => a - b).forEach((candidate) => (answer += candidate + " "));
console.log(answer);