[python] 백준 16566 카드 게임

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

16566번: 카드 게임

 

문제 해결

이진 분류로 bisect_right를 사용할 수 있는가의 문제

가장 최소의 값을 구할 때 만약 사용했다면 그 다음 수를 찾아야 하는데 여기서도 union-find를 사용하는가에 따라서 시간 단축이 될 수 있다.

만약 이전에 어떤 수를 사용했으면 그 수에 접근 했을 때 다음수로 넘어가도록 union-find를 설계할 수 있기 때문이다.

보통 bisect_left를 많이 사용해서 색다르게 느껴질 수 있는데 많이 연습하고 생각하면 충분히 풀 수 있는 문제

 

CODE

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

def find(x):
    if x!= dp[x]:
        dp[x] = find(dp[x])
    return dp[x]

def union(x,y):
    if y>=m:return

    x = find(x)
    y = find(y)
    dp[x] = y

def main():
    for num in chulsoo:
        idx = bisect_right(cards,num)
        idx = find(idx)
        print(cards[idx])
        union(idx, idx+1)

if __name__ == "__main__":
    n, m, k = map(int, input().split())
    cards = list(map(int, input().split()))
    chulsoo = list(map(int, input().split()))
    cards.sort()
    dp = [i for i in range(m)]
    main()