백준 (boj) 파이썬 - 10816 번 : 숫자 카드2

문제링크 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

*파이썬 코드

from sys import stdin

N = int(input())
arr_n = list(map(int,stdin.readline().split()))
M = int(input())
arr_m = list(map(int,stdin.readline().split()))

dic = dict()

for i in arr_n:
    try :
        dic[i] += 1
    except:
        dic[i] = 1

for i in arr_m:
    try:
        print(dic[i] , end = " ")
    except:
        print(0, end=" ")
    

 

*처음엔 이진탐색을 이용하여 문제를 해결하려고 했다. 최대한 고민하며 효율적으로 이진탐색을 구현해 봐도 게속 시간초과가 발생했고, 이유는 단일 target을 탐색할때는 당연히 이분탐색이 빠르지만, 이 문제에서는 target이 여러개 이고, 중복도 존재한다. 따라서 최초에 counting을 1번 해놓고, 탐색이 아닌 그냥 key값으로 value를 뽑아오는게 더 효율적이었다.

딕셔너리를 이용한 list 카운팅 : https://infinitt.tistory.com/78

파이썬(python) 리스트 중복 요소 개수 찾기 (카운팅) or 제거,삭제하기 (try , except , count)