백준 16566: 카드 게임

문제 요약

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

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

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

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

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

문제 분류

• 자료 구조
• 이분 탐색
• 분리 집합

문제 풀이

당연히 TreeSet같은 거로는 풀리지 않는다. 다양한 풀이 방법이 존재하지만, 나는 분리집합을 이용해서 풀었다. 이는, 분리집합에서 어떤 정점의 부모 정점을 획득할 수 있다는 특징을 이용해야 한다.
민수가 가진 m개의 각 카드들은 자신보다 낮은 숫자들을 자식으로 가진다. 즉, 어떤 숫자가 주어졌을 때 부모를 찾으면 민수가 가진 카드의 upper-bound가 되도록 분리집합을 구성하면 된다.

우선 각 숫자를 오름차순으로 자신보다 1만큼 더 큰 수를 부모로 지정한다.
그리고 민수가 가진 숫자를 최상위 노드로 지정하기 위해 0으로 만든다.
이후에 철수가 낼 카드가 주어지면, 철수와 같은 카드를 내면 안 되므로, 그 숫자보다 1큰 수의 최상위 부모를 출력하면 된다. 다음 수와 병합함으로써 카드의 소모를 처리한다.

풀이 코드

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

public class Main {
ㅔ  	static int n, m, k;
	static int p[];
	
	static int find(int v) {
		if(p[v] <= 0) return v;
		return p[v] = find(p[v]);
	}
	
	static void merge(int a) {
		int pa = find(a);
		p[pa] = find(pa + 1);
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		p = new int[n + 1];
		int v;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++)
			p[i] = i + 1;
		p[n] = 0;
		for(int i = 0; i < m; i++)
			p[Integer.parseInt(st.nextToken())] = 0;
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < k ; i++) {
			v = Integer.parseInt(st.nextToken());
			sb.append(find(v + 1)).append("\n");
			merge(v + 1);
		}
		System.out.println(sb);
	}
}