백준 10816번: 숫자 카드 2

✔ 풀이를 위한 아이디어

• collections 모듈의 Counter 클래스 활용
• 이분탐색 (Binary Search) 의 활용
  
  

✔ 코드

import sys
from collections import Counter

N = int(sys.stdin.readline())
own = list(map(int, sys.stdin.readline().split()))
cnt = sorted(Counter(own).most_common())

M = int(sys.stdin.readline())
quest = list(map(int, sys.stdin.readline().split()))

answer = []
for i in range(M):
    end = len(cnt) - 1
    start = 0
    while True:
        if start > end:
            answer.append(0)
            break
        mid = (start + end) // 2
        if cnt[mid][0] < quest[i]:
            start = mid + 1
        elif cnt[mid][0] > quest[i]:
            end = mid - 1
        elif cnt[mid][0] == quest[i]:
            answer.append(cnt[mid][1])
            break

for i in range(M):
    print("{} ".format(answer[i]), end="")
print()

• Counter 클래스의 most_common() 메쏘드까지 사용하고 나면, 등장 횟수를 기준으로 내림차순으로 정렬된다. 하지만 이분탐색을 하기 위해서는 숫자를 기준으로 오름차순으로 정렬되는 것이 편리하기 때문에 다시 sorted 함수를 활용해 정렬하였다.
• 이후에는 정렬된 cnt 리스트 안에서 이분탐색을 진행하며, 찾는 숫자가 있을 경우 그에 대응되는 등장 횟수를 출력하고, 없을 때는 0을 출력하도록 하였다.

• 동일한 코드인데 Python3로 했을 때는 안되고, PyPy3로 했을 때는 되었다.
  
  

✔ 관련 개념

• 최빈값 구하기: https://codepractice.tistory.com/71
• 이분탐색 알고리즘: https://satisfactoryplace.tistory.com/39