[백준] 16566번 - 카드 게임 (Platinum 5)

문제 링크

백준 16566번 - 카드 게임 (Platinum 5)

문제 설명

4,000,000이하의 서로 다른 자연수 M개가 쓰여진 카드와 자연수 K개가 순서대로 주어져 있다.
i번째 턴에는 i번째 자연수보다 큰 카드 중 가장 작은 카드를 낸다.
단, 이미 낸 카드를 중복해서 낼 수는 없다.
카드를 낼 수 없는 경우는 없다고 할 때, 각 턴에 내게 되는 카드를 순서대로 출력하시오.

정답 코드 및 설명

다음의 순서대로 실행하면 각 턴에 내게 되는 카드를 알 수 있다.

1. 카드의 숫자들을 cards 배열에 넣어 오름차순으로 정렬한다.
2. 첫번째 자연수보다 큰 가장 작은 카드의 숫자 cards[position]을 이분탐색을 통해 찾는다.
3. position이 포함된 집합에서 가장 큰 값 find(position)을 찾는다.
4. cards[find(position)]을 출력한다.
5. find(position)과 find(position) + 1을 하나의 집합으로 합친다.
6. 2 ~ 5의 과정을 K번 반복한다.

위의 알고리즘의 1, 2번 과정은 자연스럽게 떠올릴 수 있을 것이다.
3번과 5번 과정이 무슨 역할을 하는지 생각해보자.
이미 낸 카드를 중복해서 낼 수 없으므로 똑같은 카드를 낼 일이 생긴다면 그 다음 카드를 내야한다.
5번 과정을 통해 이미 낸 카드와 바로 다음 카드를 합쳐줌으로써, 똑같은 카드를 낼 일이 생기면 3번 과정에서 아직 내지 않은 카드 중 최소의 것을 고르도록 할 수 있다.

문제에서 준 예시를 통해 살펴보자.
M = 7, K = 5인 경우이다.

• M개의 카드 : 2 5 3 7 8 4 9
• K개의 자연수 : 4 1 1 3 8

1. M개의 카드를 정렬하면 cards[] = {2, 3, 4, 5, 7, 8, 9}가 된다.
2. 4보다 큰 가장 작은 카드의 숫자는 cards[3] = 5이다.
3. 3이 포함된 집합에서 가장 큰 값은 3이다.
4. cards[3] = 5를 출력한다.
5. 3과 4를 하나의 집합으로 합친다. 현재 집합 : {0}, {1}, {2}, {3, 4}, {5}, {6}
6. 1보다 큰 가장 작은 카드의 숫자는 cards[0] = 2이다.
7. 0이 포함된 집합에서 가장 큰 값은 0이므로 cards[0] = 2를 출력한다.
8. 0과 1을 하나의 집합으로 합친다. 현재 집합 : {0, 1}, {2}, {3, 4}, {5}, {6}
9. 1보다 큰 가장 작은 카드의 숫자는 cards[0] = 2이다.
10. 0이 포함된 집합에서 가장 큰 값은 1이므로 cards[1] = 3을 출력한다.
11. 1과 2를 하나의 집합으로 합친다. 현재 집합 : {0, 1, 2}, {3, 4}, {5}, {6}
12. 3보다 큰 가장 작은 카드의 숫자는 cards[2] = 4이다.
13. 2가 포함된 집합에서 가장 큰 값은 2이므로 cards[2] = 4를 출력한다.
14. 2와 3을 하나의 집합으로 합친다. 현재 집합 : {0, 1, 2, 3, 4}, {5}, {6}
15. 8보다 큰 가장 작은 카드의 숫자는 cards[6] = 9이다.
16. 6이 포함된 집합에서 가장 큰 값은 6이므로 cards[6] = 9를 출력한다.

9 ~ 11번 과정에서 분리 집합으로 처리한 이유가 드러나고 있다.

코드로 구현할때는 유니온 파인드 알고리즘을 사용하면 되는데, 3번 과정에 다소 주의가 필요하다.
무조건 집합의 가장 큰 원소를 찾아줘야하기 때문에, find(position) + 1이 들어있는 집합에 find(position)이 들어있는 집합을 합쳐줘야한다. 반대로 하면 find가 엉뚱한 원소를 찾게 된다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ16566 {
    int m, k;
    int[] cards;
    int[] magician;

    void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        m = Integer.parseInt(str[1]);
        k = Integer.parseInt(str[2]);
        cards = new int[m];
        magician = new int[k];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++)
            cards[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(cards);
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++)
            magician[i] = Integer.parseInt(st.nextToken());
    }

    int binarySearch(int n) {
        int start = m - 1;
        int end = -1;
        while (start > end + 1) {
            int mid = (start + end) / 2;
            if (cards[mid] > n) start = mid;
            else end = mid;
        }
        return start;
    }

    int find(int n, int[] set) {
        if (set[n] < 0) return n;
        return set[n] = find(set[n], set);
    }

    void union(int a, int b, int[] set) {
        if (b >= m) return;
        set[a] = b;
    }

    void solution() throws IOException {
        input();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] set = new int[m];
        Arrays.fill(set, -1);
        for (int card : magician) {
            int position = binarySearch(card);
            position = find(position, set);
            union(position, position + 1, set);
            bw.write(cards[position] + "");
            bw.newLine();
            bw.flush();
        }
        bw.close();
    }

    public static void main(String[] args) throws IOException {
        new BOJ16566().solution();
    }
}