16566번 - 카드 게임

1️⃣ 이분 탐색, Disjoint Set

 

✏️ 풀이 과정

기본적으로 마지막 줄에 주어지는 각각 수의 바로 다음 큰 수를 찾기 위해서는 이분탐색을 떠올리기 쉽습니다. 그러나 문제는 이분탐색으로 낼 카드를 찾으면 해당 카드를 지워야 하는데 배열을 사용할 경우 이 과정이 O(M)이 되어서(인덱스 하나를 지우고 뒷부분을 옮겨주는 데 걸리는 시간복잡도) 전체적으로 O(K*M*logM)이 되어서 시간이 초과된다는 것입니다.

 

이 문제를 해결하기 위해 Disjoint Set을 사용해서 O(1)만에 중복되지 않는 다음 수를 찾는 방법을 사용해야 합니다. 기본적인 아이디어는 이분탐색으로 낼 수를 찾았을 때 이 것의 바로 다음 수와 연결시킨다는 것입니다. 가령 3,5가 있었고 2가 주어져서 3을 내야 한다고 쳤을 때 3과 5를 연결해줍니다. 그러면 다음 번에 3이 다시 들어온다고 치면 이번 역시 3을 내야 한다는 결과를 이분 탐색으로부터 얻겠지만 여기서는 find(3)을 가져옴으로써 바로 다음 순서인 5가 나오게 되는 것입니다. 만약 5도 사용되었을 경우에는 5의 부모인 더 큰 수가 나올 것이므로 중복에 대해 걱정할 필요는 없습니다.(항상 비어있는 무언가가 root로 잡히게 됩니다.)

 

이를 for문 내에서 적용하는 순서를 살펴보면 먼저 이분탐색으로 바로 다음 자리를 가져옵니다.(pos) 그리고 find 메서드에 pos를 인자로 주어 이보다 같거나 큰 것 중 아직 사용되지 않은 수의 인덱스를 가져옵니다.(nextPos) 마지막으로 다음 번의 사용을 위해 이 nextPos와 nextPos+1을 연결시켜주고(nextPos+1이 사용되었어도 그와 연결된 root와 최종적으로 연결됩니다.) 지금 낸 cards[nextPos]를 결과 배열에 넣어주면 됩니다.

 

이를 K번 반복한 후 배열의 내용을 한 줄씩 출력하면 문제가 해결됩니다.

 

주의할 점은 부모 자식 관계를 명확하게 해야하기 때문에 rank를 사용해서 계산량을 줄이는 테크닉을 사용해서는 안됩니다.(상하관계가 흐트러지기 때문에) 또한 union을 할 때도 항상 부모와 자식의 위치를 고정시켜야 합니다.

 

⏱ 시간 복잡도

이분 탐색을 K번 시행하기 때문에 대략 O(KlogM)의 시간 복잡도가 필요합니다. 여기에 더해 Disjoint Set을 위한 계산 시간이 필요하지만 이는 O(K)에 가깝습니다. 결과적으로 M이 4000000일 때도 문제 없이 작동합니다.

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const [N, M, K] = input[0].split(" ").map(Number);
const cards = input[1].split(" ").map(Number);
const incomming = input[2].split(" ").map(Number);

const parents = Array.from(Array(N), (_, i) => i);
const find = (a) => {
    if (parents[a] === a) {
        return a;
    }
    return (parents[a] = find(parents[a]));
};
const union = (a, b) => {
    let aRoot = find(a);
    let bRoot = find(b);
    if (aRoot === bRoot) {
        return false;
    }
    parents[bRoot] = aRoot;
    return true;
};

cards.sort((a, b) => a - b);

const upper = (left, right, target) => {
    let mid;
    while (left < right) {
        mid = Math.floor((left + right) / 2);
        if (cards[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return right;
};

const ans = [];
for (let i = 0; i < K; i++) {
    const pos = upper(0, M - 1, incomming[i]);
    const nextPos = find(pos);
    union(nextPos + 1, nextPos);
    ans.push(cards[nextPos]);
}

console.log(ans.join("\n"));