[백준/Java] 16566 : 카드 게임

📌 문제 정보

• 번호: 16566
• 제목: 카드 게임
• 난이도: Gold 1
• 분류: 자료구조, 분리 집합(Union-Find)

---

💡 접근 방식

민수의 카드보다 큰 철수의 카드 중 가장 작은 카드를 찾는 문제입니다.
단순 반복문 → TreeSet → Union-Find 순으로 최적화했습니다.

---

🔹 1단계 – 단순 반복문 O(K×N)

for (int j = card + 1; j <= N; j++) {
    if (cards[j] == 1) {
        sb.append(j).append("\n");
        cards[j] = 0;
        break;
    }
}

N이 최대 4,000,000이라 시간초과

---

🔹 2단계 – TreeSet O(K×logN)

TreeSet<Integer> cards = new TreeSet<>();
int result = cards.higher(card);
cards.remove(result);

Integer 객체 기반이라 메모리 접근 비용이 커서 시간초과

---

🔹 3단계 – Union-Find O(K×α(N)) ≈ O(1)

카드를 제거하는 대신 "다음 카드로 가라"고 포인터만 변경

철수 카드 있는 칸 → parent[i] = i
철수 카드 없는 칸 → parent[i] = i + 1

카드 사용 후 parent[result] = result + 1 로 설정하면
다음에 같은 카드를 찾을 때 find()가 자동으로 다음 카드로 이동

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

---

💻 핵심 코드

// 카드 없는 칸은 다음으로 넘기기
for (int i = 1; i <= N; i++) {
    if (cards[i] == 0) parent[i] = i + 1;
}

// 민수 카드 처리
int nextCard = find(card + 1);
parent[nextCard] = nextCard + 1;

---

⏳ 복잡도 분석

방법	시간 복잡도	결과
반복문	O(K×N)	시간초과
TreeSet	O(K×logN)	시간초과
Union-Find	O(K×α(N))	통과

• 공간 복잡도: O(N)

---

📄 전체 코드

package B16566;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, K;
    static int[] cards;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cards = new int[N + 1];
        parent = new int[N + 2];
        for (int i = 1; i <= N + 1; i++) {
            parent[i] = i;
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            cards[Integer.parseInt(st.nextToken())]++;
        }
        for (int i = 1; i <= N; i++) {
            if (cards[i] == 0) {
                parent[i] = i + 1;
            }
        }
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < K; i++) {
            int card = Integer.parseInt(st.nextToken());
            int nextCard = find(card + 1);
            parent[nextCard] = nextCard + 1;
            sb.append(nextCard).append("\n");
        }
        System.out.print(sb);
    }

    static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
}