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

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

 

---

■ 문제

---

■ 문제 이해

1부터 N까지 번호가 매겨져 있는 카드가 있고, 철수는 이 카드들 중에서 K개를 골라 제출한다.

민수는 철수가 낼 카드를 미리 알고 있고, M개의 카드를 사용하여 모든 차례에서 승리해야 하는 게임이다.

 

이때, 민수가 카드를 내지 못하는 경우는 없으며 철수가 내는 카드는 1 ~ N 범위다.

 

문제에서 조심해야 할 부분은 철수는 카드를 뛰어난 마술사이기 때문에 카드를 중복으로 낼 수 있다는 점이고, 민수는 평범한 머글이기 때문에 냈던 카드는 중복으로 낼 수 없기에 가지고 있는 카드를 한 번씩만 사하여 게임에서 이겨야 한다.

---

■ 풀이

M은 4,000,000, K는 1,000까지이며, 시간제한은 1.2초이기 때문에 완전탐색으로는 풀 수 없는 문제다.

 

따라서, 민수의 카드를 오름차순 한 후 이분 탐색으로 낼 카드를 탐색했다.

 

게임을 이기기 위해선 철수보다 높은 카드를 내야 하기 때문에 특정 key 값보다 처음으로 큰 값의 위치를 찾는 Upper Bound로 풀었다.

 

우선 이분 탐색을 사용하기 위해 민수의 카드를 오름차순 했다.

 

 

철수의 첫 번째 카드인 4를 이길 수 있는 카드 중 가장 작은 수를 찾아보자.

그다음, 두 번째 카드인 1을 이길 수 있는 카드를 찾아보자.

그 다음, 세 번째 카드인 1을 이길 수 있는 카드를 찾아보자.

1을 이길 수 있는 카드 중 가장 작은 수 2를 찾았지만, 민수는 평범한 머글이기 때문에 냈던 카드를 또 낼 수 없다.

 

단순히 냈던 카드를 삭제하는 방법은 O(n)의 시간 복잡도가 나오기 때문에 시간초과가 나올 것이다.

 

냈던 카드 인덱스와 냈던 카드의 바로 다음 인덱스를 하나로 묶기 위해, Union-Find 알고리즘을 이용했다.

 

그림을 보자,

위에 그림처럼 민수의 카드 index를 저장하는 배열을 하나 만들어주고, 낸 카드 index와 바로 다음 index를 union 하며 게임을 진행해 보자.

철수가 4를 내면 이분 탐색으로 카드를 찾은 민수는 5를 내고, 5에 해당하는 index(3)을 5의 바로 다음 인덱스 (index + 1)와 union 한다.

다음, 민수는 2를 내고, 2에 해당하는 index(0)을 바로 다음 인덱스 (index + 1)와 union 한다.

다음, 왼쪽 그림을 보면 민수는 2를 내야 한다. 이때, find로 카드 2에 해당하는 인덱스를 찾는다.

2에 해당하는 인덱스는 1이기 때문에 3을 반환하면 되고, 3 또한 사용한 카드이기 때문에 오른쪽 그림과 같이 바로 다음 index와 union 한다.

 

- 코드

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

public class Main {
	// 카드의 index를 담을 배열
    static int[] link;

    public static void main(String[] args) throws Exception {
        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());

        link = new int[m];
        int[] cards = new int[m];

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

        Arrays.sort(cards);

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            int value = Integer.parseInt(st.nextToken());
            int low = 0;
            int high = m;

            // upper bound
            while (low < high) {
                int mid = (low + high) >>> 1;

                if (cards[mid] <= value) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }

            int index = find(low);
            if (index + 1 != m) {
                union(index, index + 1);
            }

            sb.append(cards[index]).append("\n");
        }

        System.out.println(sb);
    }

    private static void union(int from, int to) {
        int fromLink = find(from);
        int toLink = find(to);

        link[fromLink] = link[toLink];
    }

    private static int find(int n) {
        if (link[n] == n) {
            return n;
        }

        return link[n] = find(link[n]);
    }
}

 

전형적인 Union-Find 알고리즘을 사용하기 위해 코드처럼 union을 사용하였지만, index와 index + 1은 같은 집합일 수 없기 때문에 생각해 보면 찾은 수의 index만 find(low)로 찾고, 다음 인덱스와 연결하면 된다.

 

다음 코드처럼 변경할 수 있다.

// 이전 코드

			int index = find(low);
			if (index + 1 != m) {
				link[index] = link[index + 1];
			}

			sb.append(cards[index]).append("\n");
		}

		System.out.println(sb);
	}

	private static int find(int n) {
		if (link[n] == n) {
			return n;
		}

		return link[n] = find(link[n]);
	}
}

 

최근에 운영 중인 동아리에서 좋은 인사이트를 얻어 작성해 보았습니다!