백준 16566 카드 게임

16566 카드 게임

문제

숫자가 적힌 카드로 게임을 한다.
번갈아 가며 카드를 내는데 상대가 내는 카드보다 큰 카드를 내야하며,
낼 수 있는 카드 중에 가장 작은 카드를 내는 전략을 사용한다.
내가 가진 카드의 종류와 상대가 내는 카드의 순서가 입력으로 주어질 때
내는 카드의 순서를 출력한다.
한 번 낸 카드는 다시 낼 수 없다.

카드의 수는 400만개 이하, 제출하는 횟수는 1만회 이하

예
내가 가진 카드

2 5 3 7 8 4 9

상대가 내는 카드 순서

4 1 1 3 8

내가 내는 순서

5
2
3
4
9

풀이

일단 내가 가진 카드를 정렬해둔다.
카드의 수가 400만개로 많아서 매번 하한을 찾으면 안 된다.
이미 사용한 카드는 바로 다음으로 큰 카드에 연결시켜 다음 방문시 탐색을 빠르게 하도록 한다.(union-find 알고리즘. 최소신장트리를 찾을 때 썼던 크루스칼 알고리즘에서도 썼었다.)
여기에 이분탐색 섞어주면 된다.

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

cards.sort()

def bin_search(target):
    lo, hi = -1, M-1

    while lo+1 < hi:
        mid = (lo+hi) // 2
        if cards[find(mid)] > target:
            hi = mid
        else:
            lo = mid

    return hi

def find(idx):
    if isinstance(cards[idx], int):
        return idx
    else:
        root = find(cards[idx][0])
        cards[idx] = root,
        return root

for r in reqs:
    ideal = bin_search(r)
    real = find(ideal)
    print(cards[real])
    if real+1 < M:
        cards[real] = real+1,