이진 탐색(이분 탐색): 백준 10816 파이썬

문제:

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

10816번: 숫자 카드 2

 

정답:

1. collections 모듈의 Counter 클래스 사용

import sys
from collections import Counter

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_arr = list(map(int, sys.stdin.readline().split()))

cnt = Counter(n_arr)

for i in m_arr:
    print(cnt[i], end=' ')

 

2. 딕셔너리 사용

mport sys
from collections import Counter

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_arr = list(map(int, sys.stdin.readline().split()))

dic = dict()

for i in n_arr:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1

for i in range(m):
    if m_arr[i] in dic:
        print(dic[m_arr[i]], end=' ')
    else:
        print(0, end=' ')

 

풀이:

이진 탐색으로 문제를 풀려고 접근했었는데 세 번의 시도 모두 시간초과가 나왔다.

내장함수인 count() 함수를 사용했을 때도 시간초과가 나왔다.

질문 검색 딕셔너리를 사용하면 시간을 줄일 수 있다는 힌트를 얻어 먼저 각 원소의 개수를 딕셔너리 형태로 반환시켜 주는 Counter 클래스를 떠올렸고 아주 간단하게 해결할 수 있었다.

 

딕셔너리를 직접 사용해서도 해결이 가능했다. 

 

구글링을 해서 이진 탐색으로 푸는 방법을 알아내려고 했었는데, 대부분의 사람들이 나처럼 이진 탐색으로 접근했다가 시간 초과가 발생하고 결국 딕셔너리로 해결했어서 찾지 못했다.