Q. 16566 자바 : 카드 게임

Q. 16566 자바 : 카드 게임

 

문제 : boj.kr/16566

P5 난이도의 문제이다.

 

문제를 간단히 설명하자면

카드 더미가 주어진다. 이 때 상대는 나와 동일한 카드 더미를 가진다.

그리고 상대의 카드가 주어질 때 상대의 카드보다 크면서 이전에 낸 적 없는 가장 작은 카드를 출력하는 문제이다.

---

먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.

1. 상대의 카드보다 크면서 이전에 낸 적 없는 카드 중 가장 작은 카드를 카드 더미에서 찾는다.

2. 사용한 카드는 사용했다고 처리한다.

3. 1~2 과정을 반복한다.

 

이렇게 푼다면 낼 수 있는 카드를 찾을 때 N^2번의 연산이 생기고,

이전에 낸 적 없는 카드를 찾는데 최악의 경우 N번의 연산이 생기므로 총 N^3 * K의 시간복잡도를 가지게 된다.

시간제한은 1.2초이므로 이 방법은 불가능해 보였다.

 

K는 어쩔 수 없지만, N의 경우 N log N 정도로 시간복잡도를 줄여야 한다.

---

이 문제에서 중요한 점은 두 가지이다.

1. 상대방의 카드보다 크면서 가장 작은 카드를 카드 더미에서 찾는다. - 이분 탐색 O(N log N)

2. 이전에 사용했던 카드는 사용할 수 없다. - untion-find O(1)

 

1번 과정은 이분 탐색을 사용한다면 N log N의 시간 복잡도로 탐색 시간을 줄일 수 있다.

 

2번 과정도 N번의 연산이 필요하고, 이를 줄이기 위한 아이디어를 떠올리는데 어려웠다.

핵심 아이디어는 n번 카드가 이미 사용됬다면, 그 다음에 사용할 수 있는 카드는 n+1번 카드라는 점 이다.

union-find를 사용한다면 이 연산을 상수 시간으로 줄일 수 있다.

---

처음에는 모든 카드가 사용되지 않았으므로 부모를 나 자신으로 갖는다. - parent[i] = i

1번 과정으로 카드를 사용했다면 사용한 카드의 부모는 내 다음 카드로 대입한다. - union(n, n+1)

이 때 n + 1이 전체 카드 숫자의 범위를 초과할 수 있으므로 예외 처리가 필요하다.

 

2번의 연산 속도는 상수이므로 전체 시간 복잡도를 O(K*N logN)으로 줄일 수 있다.

 

코드는 아래와 같다.

import java.io.*;
import java.util.*;

class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
    static StringTokenizer st;

    static int n, m, k, curSubmit;
    static int[] cards, submits, parents;

    static void input() throws IOException{
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        cards = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        submits = new int[k];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            submits[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void pro() {

        Arrays.sort(cards);
        parents = new int[m];
        for (int i = 0; i < m; i++) parents[i] = i;

        for (int i = 0; i < k; i++) {
            curSubmit = submits[i];
            int result = 0;

            int left = 0, right = m - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                int available = find(mid);

                if (determination(cards[available])) {
                    result = available;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            sb.append(cards[result]).append('\n');
            if (result + 1 != m) union(result + 1, result);
        }
        System.out.println(sb);
    }

    static int find(int p) {
        if (parents[p] == p) return p;
        return parents[p] = find(parents[p]);
    }
    
    static void union(int a, int b) {
        int aParent = find(a);
        int bParent = find(b);

        parents[bParent] = aParent;
    }

    static boolean determination(int element) {
        return curSubmit < element;
    }

    public static void main(String[] args) throws Exception{
        input();
        pro();
    }
}