백준 16566 [카드 게임]

문제

철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.

1. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
2. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
4. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.

철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.

민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.

K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

입력

첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))

다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.

다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.

출력

K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.

 

https://www.acmicpc.net/problem/16566

16566번: 카드 게임

 

---

 

 카드 게임은 상대가 낸 카드보다 큰 카드들 중 가장 작은 카드를 찾아 내야하는 문제이다. 이분 탐색을 이용하면 시간 복잡도를 많이 줄일 수 있지만 이번 문제는 그것 포함 한번 낸 카드는 낼 수 없기 때문에 최적화가 추가로 필요하다.

 예를 들면 카드가 4,000,000까지 주어지기 때문에 이분 탐색으로 내야할 카드를 금방 찾았다해도 그 카드를 삭제하기 위해 작업이 추가로 필요하다. 만약 배열에 카드를 담았다면 낸 카드 처리를 배열 내에서 어떻게 처리할지 고민해봐야하고, ArrayList에 카드를 담았다면 낸 카드를 remove함수로 제거할 수 있지만 이는 시간복잡도 O(n)만큼 걸리므로 시간초과에 걸릴 것이다. 

 이를 해결하기 위해 나는 Union-Find를 이용하였다. 백준에 나와있는 테스트케이스를 통해 처리방법을 알아보자.

 

우선 배열에 주어진 M개의 카드를 담고 오름차순으로 정렬해준다.

index	0	1	2	3	4	5	6
card	2	3	4	5	7	8	9

 

그리고 union-find를 위한 배열 g를 준비한다. (g의 요소는 본인의 index를 value로 갖는다)

index	0	1	2	3	4	5	6
g	0	1	2	3	4	5	6

 

예제에 나와있는 순서로 철수가 카드를 내기 시작한다.

 

1. 우선 카드 4를 낸 경우 이분 탐색을 하면 카드 5가(index = 5) 내야할 카드로 나온다.

이렇게 카드를 내면 우선 find(index)를 통해 index를 초기화해준다. find(5) = 5이므로 index는 그대로 5가 된다.

그 후 본인 index + 1와 union을 통해 하나의 집합으로 합친다. (union(5 , 6))

(이번 문제에서 사용하는 union은 본인보다 큰 g[index] 집합에 합쳐진다)

index	0	1	2	3	4	5	6
g	0	1	2	3	4	6	6

 

2. 두번째로 1을 낸 경우 이분 탐색을 하면 카드 2가(index = 2) 내야할 카드로 나온다.

아까와 같이 find(2) 를 통해 index를 초기화해준다. find(2) = 2이므로 index는 그대로 2가 되고 union(2, 3)을 한다.

index	0	1	2	3	4	5	6
g	0	1	3	3	4	6	6

 

3. 세번째로 1을 또 낸 경우 이분 탐색을 하면 두번째와 같이 카드 2가(index = 2) 내야할 카드로 나온다.

카드 2는 아까 냈기 때문에 find(2)를 통해 내야할 카드의 index를 구하면 index = find(2) = 3이 나온다.

따라서 카드 3을 내고 union(3, 4)를 해준다.

index	0	1	2	3	4	5	6
g	0	1	3	4	4	6	6

 

4. 네번째로 3을 낸 경우 이분 탐색을 하면 카드 4가(index = 4) 내야할 카드로 나온다.

find(4) = 4이므로 union(4, 5)를 해준다.

index	0	1	2	3	4	5	6
g	0	1	3	4	6	6	6

 

5. 마지막으로 8을 낸 경우 이분 탐색을 하면 카드 9가(index = 6) 내야할 카드로 나온다.

find(6) = 6이므로 union(6, 7)을 해준다.

여기서 설명할 때는 배열 g를 index = 6까지만 만들었지만 실제로는 g의 크기를 M + 1로 해줘서 index 초과 오류를 피해야 한다.

 

실제 구현한 코드는 다음과 같다.

 

import java.io.*;
import java.util.*;
public class Main {
    static int[] g;
    static int find(int x){
        if (g[x] == x) return x;
        return g[x] = find(g[x]);
    }
    static boolean union(int x, int y){
        int a = find(x);
        int b = find(y);
        if (a == b) return false;
        else if (a > b)
            g[b] = a;
        else
            g[a] = b;
        return true;
    }
    static int binarySearch(int[] arr, int num){
        int l = 0;
        int r = arr.length - 1;
        while (l <= r){
            int mid = (l + r) / 2;
            if (num >= arr[mid])
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[M];
        g = new int[M + 1];
        for (int i = 0; i < M; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            g[i] = i;
        }
        g[M] = M;
        Arrays.sort(arr);
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < K; i++){
            int num = Integer.parseInt(st.nextToken());
            int index = binarySearch(arr, num);
            index = find(index);
            sb.append(arr[index] + "\n");
            union(index, index + 1);
        }
        System.out.print(sb);
    }
}