[구현] 백준 10816: 숫자 카드 2 (Python)

BOJ 10816 숫자 카드 2

시간 복잡도가 관건

정답 코드

n = int(input())
num = list(map(int, input().split()))

m = int(input())
find_num = list(map(int, input().split()))

dic = {}

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

for i in find_num:
  if i in dic:
    print(dic[i], end = " ")
  else:
    print(0, end = " ")

풀이과정

시간복잡도를 줄이기 위해 딕셔너리를 사용했습니다.

이분탐색을 사용하려고 했는데 이거 뭐 정렬해서 하는게 그럴 필요가 있는건가 싶어서 시도하지않았습니다.

find_num에 입력된 정수가 num에 몇개를 있는지 세기 때문에
num에서 각 요소당 개수가 몇개인지 우선 셉니다.

예시 입력을 입력하고 dic을 출력해보면 이렇게 출력됩니다.
{6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}

이제 여기서 num을 순회하며 이 dic에 num에 해당하는 값이 몇개인지 셉니다.

num = 10 9 -5 2 3 4 5 -10

10은 3개 9는 없으므로 0.. 이런식ㅇ로 숫자를 세주기만 끝납니다.
순회를 돌며 이 값이 딕셔너리에 들어있는지 아닌지만 셉니다.

Counter 모듈을 사용하는 방법도 있다고하지만 사용하고 싶지 않았습니다.

오답 코드 (처음에 풀이했던 코드)

n = int(input())
num = list(map(int, input().split()))

m = int(input())
find_num = list(map(int, input().split()))

cnt_list = []

for i in find_num:
  cnt = 0
  for j in num:
    if j == i:
      cnt += 1
  cnt_list.append(cnt)
    
print(" ".join(map(str, cnt_list)))

처음 문제를 보고 바로 입력을 받아서 이중 for문을 순회하면서 cnt를 추가하였는데 시간초과가 일어났습니다.
이중 for문으로 인해서 시간 초과가 나는 것 같아 시간복잡도를 줄이기 위해 시도했습니다.