[백준✨] 16566번 <카드 게임> / Python 문제풀이 /

해답)

import sys
import math

def input():
    return sys.stdin.readline().rstrip()

'''
@@@ 입력받기 @@@
'''
N, M, K = map(int, input().split())
cards = list(map(int, input().split()))
targets = list(map(int, input().split()))

'''
@@@ 필요한 자료구조 @@@
'''
sqrt_N = int(math.sqrt(N))
cards_presence = [0] * (N+1) # 해당 카드가 존재하는지
dummy = [0] * (sqrt_N+1) # 인덱싱을 하는 역할

for c in cards:
    cards_presence[c] += 1
    dummy[c // sqrt_N] += 1


'''
@@@ 알고리즘 구현 @@@
'''
for t in targets:
    will = t + 1 # 이번 차례에 낼 카드 후보
    while dummy[will // sqrt_N] == 0 and will <= N:
        will = ((will // sqrt_N) + 1 ) * sqrt_N
    if will > N:
        will = 0 # 낼게 아에 없었다? 제일 작은 것 내자.
        while dummy[will // sqrt_N] == 0 and will <= N:
            will = ((will // sqrt_N) + 1 ) * sqrt_N
    while True:
        if cards_presence[will] != 0 :
            cards_presence[will] -= 1
            dummy[will // sqrt_N] -= 1
            print(will) # 카드 내기
            break
        will += 1
    

---

풀이)

이 문제의 핵심포인트는 N, M 은 최대 400만까지 가는 매우매우 큰 수임에 반해,  자연수 k 는 최대 1만개밖에 되지 않는다는 점입니다. 

그러므로, 단순히 주어진 카드들을 정렬을 하거나, 이진 트리로 만드는 방법을 쓰더라도 최소 O(NlogN) 의 시간복잡도가 되어버려 시간초과가 나고 맙니다! 😅

 

입력을 받을 떄, 해당 자료 여부를 더 큰 단위로 판단해줄 dummy 배열을 만들어줍니다.

예를들어 내가 100개 자료씩 묶었다고 가정해봅시다.

dummy[0] 은 0~99 에 해당하는 카드가 몇 개 있는지, 

dummy[1] 은 100~199 에 해당하는 카드가 몇 개 있는지를 알려줍니다.

이 더미 배열의 사이즈는 총 카드 수의 루트로 해주는 것이 가장 효율적입니다.

 

위 방식으로 자료를 입력받아 놓고, 낼 수 있는 카드를 dummy 단위로 판단합니다.

해당 카드의 dummy가 비어 있다면, 다음 dummy 를 판단하므로 훨씬 빨라지겠죠?

시간복잡도는 대략 o(N + k*2sqrt(N)) 정도가 되겠네요!

* 예를들어, 5 안되면 6, 안되면 7 ,,,, 이런 방식이 아니라, 더미 1(카드 5) 안되므로 더미2(카드 101)

 

요약 

1. 카드 유무의 존재를 알려주는 cards_presence 를 저장하고 dummy 형태로 묶은 형태 또한 저장한다.

2. target 카드 번호보다 1을 더 큰 것을 첫 후보로 잡고, 해당 카드의 dummy가 비어있는지 테스트한다.

   2-1. 비어있다면, 다음 더미를 확인하고, 더 큰 더미에 모두 카드가 없다면, 카드 후보를 0 으로 설정하고 다시 탐색한다.

   2-2. 비어있지 않다면, 1씩 더해주며 cards_presence 를 탐색해, 낼 카드를 골라준다. 

 

* pypy3 로 제출해야 통과가 됩니다.

 

 

 

 

* 위 문제의 저작권은 백준(https://www.acmicpc.net/) 에 있습니다.