새싹프로그래머의 이야기

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

문제: 주어진 숫자 카드에 대해서, 각 수가 적혀진 숫자카드가 몇장 있는지 출력하는 문제입니다.

풀이 방법: heapq를 사용했습니다. 

이진 탐색 문제인 것은 알았습니다.

다만, 주어진 값들을 count 하면 되는 문제이므로 heapq.heappop()이 이진 탐색과 같은 log의 시간 복잡도를 갖는다는 것을 활용하였습니다.

풀이 코드:

import heapq
import sys

MAX = 10000000 * 2 + 2

n = int(sys.stdin.readline().rstrip())
lst = list(map(int,sys.stdin.readline().rstrip().split()))

m = int(sys.stdin.readline().rstrip())
lst2 = list(map(int,sys.stdin.readline().rstrip().split()))

count = [0] * MAX

while lst:
    count[heapq.heappop(lst)] += 1


for i in range(m):
    print(count[lst2[i]],end = ' ')