[백준 16566번] 카드 게임 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_right

def findparent(x):
  if check[parent[x]]==0:
    return parent[x]
  else:
    parent[x] = findparent(parent[x])
    return parent[x]

N,M,K = map(int,input().split())

minsu = [*sorted(map(int,input().split()))]
cheolsu = [*map(int,input().split())]

check = [0]*M

parent = {i:i+1 for i in range(M)}

for i in range(K):
  card = cheolsu[i]
  idx = bisect_right(minsu,card)
  if check[idx] == 0:
    check[idx] = 1
    print(minsu[idx])
  else:
    idx = findparent(idx)
    check[idx] = 1
    print(minsu[idx])

 

공항 문제를 풀지 않았다면 어려웠겠지만 공항 문제를 풀고난 나에게는 너무나 가소로웠던 문제이다.

공항문제에 이진탐색만 살짝 섞인 느낌으로 풀어주면 된다.

 

요약하면

1. 민수의 카드를 크기순으로 정렬한다.

2. 이진탐색으로 철수의 카드보다 큰 카드를 불러온다.

3. 이때 이미 낸 카드라면 공항 문제에서처럼 union-find를 이용해 다음 카드를 불러온다.

 

공항보다 두 티어나 높을 필요가 있는 문제인가? 싶은 문제였다.

그리고 이진탐색을 바로 전 문제인 가장 긴 증가하는 부분수열 문제에서 bisect를 활용하면 된다는 것을 알게 되어서 아주 간단하게 구현할 수 있었다.

 

 

오늘의 교훈) bisect를 활용하자