[백준] 16566 - 카드 게임 (P5)

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

16566번: 카드 게임

이분 탐색을 쓰면 좋겠다고 떠올렸지만, 한번 쓴 카드를 다시 쓰지 않도록 체크하는 부분을

어떻게 해야할지 떠올리지 못했던 문제이다.

결국 알고리즘 분류를 통해 힌트를 얻고 풀었다.

 

분리집합을 보고 처음에는 어떻게 분리집합을 이용해서 풀 수 있을지 감이 안잡혔는데,

노트에 생각을 정리하다보니 아이디어가 떠올랐다.

 

이분탐색, 특히 upper bound 를 활용해야 하는 상태에서, 특정수를 이미 썼다면,

아직 사용하지 않은 카드들 중 그 수 바로 다음으로 큰 수를 찾아야 한다.

이걸 분리집합으로 묶어주면 된다.

 

10 7 5
2 5 3 7 8 4 9
4 1 1 3 8

이 예제 입력1 을 예시로 들어보자.

M개의 뽑은 카드를 정렬하면

2 3 4 5 7 8 9

이렇게 7개의 숫자가 있다.

 

1. 맨처음 4보다 큰 수를 upper bound 로 찾으면 5가 나온다.

5를 출력하고, 앞으로 upper bound 로 5를 필요로 할 때마다

5보다 바로 다음으로 큰 수인 7일 가리킬 수 있도록 둘을 연결해주어야 한다.

 

이 연결하는 작업을 5의 parent를 7로 설정하여 일종의 분리집합 구성을 해둔다.

그 동안 분리집합 자료구조를 일종의 set 자료구조처럼만 생각을 했는데,

이렇게 부모-자식 사이의 관계의 연결성으로 활용하는 아이디어는 처음 떠올려보았다.

따라서 앞으로 upper bound로 5를 가리키면, 해당 5의 부모를 찾아 그 부모를 출력하도록 하면 된다.

 

2. 다음으로 3을 내면, 3의 upper bound 인 4를 낸다. 앞서 설명한대로 분리집합을 활용했으므로

3의 upper bound 인 4를 구하고,

이 4의 부모를 찾기위해 4에 대해 find 연산을 수행하고, 그 결과값인 4를 출력한다.

이제 앞으로 4를 가리킬 때마다 4 바로 다음으로 큰 5를 가리키도록

5를 집합의 대표로하여 4와 union 한다.

 

.... 이하 반복 .....

 

---

사실 python 기준으로는 구현 난이도가 크게 높지 않았다.

질문게시판을 보니 C++로는 최적화가 어느정도 필요해보였다.

그래서 난이도가 플레티넘까지 올라간게 아닐까 조심스레 예측해본다.

(난 개인적으로 아이디어가 어렵다고 생각해 골드2~골드1 정도로 체감되었다.)

 

def find(x):
    if x == prt[x]:
        return x
        
    v = find(prt[x])
    prt[x] = v
    return v

def union(x, y):
    if y >= m:
        return
        
    x = find(x)
    y = find(y)
    prt[x] = y

def upper_bound(x):
    s, e = 0, m
    while s < e:
        mid = (s+e)//2
        if nums[mid] > x:
            e = mid
        else:
            s = mid + 1

    return e

n, m, k = map(int, input().split())
nums = sorted(map(int,input().split()))
prt = [i for i in range(m)]
seq = list(map(int, input().split()))
for num in seq:
    idx = upper_bound(num)
    idx = find(idx)
    print(nums[idx])

    union(idx, idx+1)

 

난 구현할 때, 처음에 값을 기준으로 분리집합을 구성했는데,

이분탐색이 인덱스를 기준으로 하다보니 값과 인덱스 사이에 연결 요소가 필요해져서

그냥 값이 아닌 인덱스를 기준으로 분리집합을 구성했다.