백준 16566번 : 카드 게임 [자바]

 

🧫 문제 분석

 

✔️ 출처

카드 게임 플래티넘 5

 

📖 문제

 

 

이분탐색 + 유니온 파인드 (서로소 집합)문제

 

문제의 핵심은

철수는 카드를 조작해서 낼 수 있고, 같은 수여러개를 낼 수 도 있음

민수는 철수의 카드를 미리 알고 철수가 낸 카드 중 더 큰 수에서 가장 작은 수를 낸다.

 

문제에서 민수가 카드를 내지 못하는 경우가 없다고 가정하였으므로

철수가 낸 카드보다 작거나 같은 카드만 남을 경우가 없다는 의미이다.

즉, 철수보다 항상 더 큰 카드 k 개 만큼 내어 항상 승리한다

 

철수가 낸 카드에 맞게 민수는 자신의 카드에서 적절한 카드를 이분탐색으로 찾아서 낸다.

찾은 카드가 철수가 낸 카드와 같다면 그 다음 카드를 가리킨다. 

사용한 카드는 그 다음 카드의 대표 집합에 연결한다. 

 

다음 카드의 대표 집합을 연결하는 방법은 서로소 집합을 이용한다. 

다음 카드도 사용했을 수 있으므로 사용가능한 다음카드의 대표집합(부모) 을 찾는다.  : find() 

현재 카드를 사용한 뒤에는 다음 카드로 연결한다 : union()

 

 

 

 

M과 N이 400만개이므로

Arrays.sort()로 정렬시 최악의 경우 N*log(N)가 소요된다. 

log2(400만) ≈ 22 * 400만  = 대략 8,400만 정도이다. 

여기에 이분탐색 + 경로 압축까지하면 

시간복잡도는 꽤 높다. 

 

하지만 통과하긴한다.

 

N까지 배열을 만든 후 존재 마킹 기반 정렬시  O(N)에 처리할 수 있다.

이는 Arrays.sort() 보다 2배 빠른 속도를 보여준다.

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] cards = new int[m];
        boolean[] arr = new boolean[n + 1];
        parent = IntStream.range(0, n + 1).toArray();

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[num] = true;
        }

        int idx = 0;
        for (int i = 1; i <= n; i++) {
            if (idx == m) break;
            if (arr[i]) cards[idx++] = i;
        }


        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            int target = Integer.parseInt(st.nextToken());
            // 이분 탐색
            int left = 0, right= m - 1;
            while (left < right) {
                int mid = (left + right) >>> 1;

                if (cards[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }


            // 같은 값이면 안되고 더 큰 값중 가장 작은 값이여야하므로 바로 다음 칸의 값을 가리킴
            if (cards[left] == target) {
                left++;
            }

            int current = find(left); // 사용하지 않은 카드 찾기
            sb.append(cards[current]).append("\n"); // 카드 사용

            if (current + 1 < m) {
                union(current, current+1); // 현재 카드는 사용하였으므로 다음 카드의 집합으로 추가한다. 
            }
        }
        System.out.print(sb.toString());
    }

    // a 는 현재 선택된 카드, b는 그 다음 카드
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);

        parent[a] = b;
    }

    // 경로 압축
    private static int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.