10816: 숫자 카드 2 - Python

문제

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

풀이 1 (bisect)

import bisect

N = int(input())
N_list = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))

for x in M_list:
    print(bisect.bisect(N_list, x) - bisect.bisect_left(N_list, x), end = " ")

• 지난 문제에서 알게된 bisect를 사용했다. 편리하군~
• bisect 사용을 위해 N_list를 정렬하는 것을 잊지 말자.

시간 복잡도는 다음과 같이 계산할 수 있다.

• N_list를 정렬: O(N log N)
• N개 원소를 갖는 리스트에 대해 bisect(), bisect_left()를 M번 수행: O(log N) * M = O(M log N)
  -> 총 시간 복잡도: O(N log N + M log N)

풀이 2 (dictionary)

import bisect

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))
dic = {}

for n in N_list:
    if n in dic:
        dic[n] += 1
    else:
        dic[n] = 1

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

• 이 코드를 참고하였다.
• N개의 수를 순회하며 dic에 빈도수 기록: O(N)
• M개의 수를 순회하며 dic 조회: O(M)
  -> 총 시간 복잡도: O(M + N)

---

오늘의 교훈

• 시간 복잡도를 외우고 이해하자.
  • sort(): O(N log N)
  • bisect(): O(log N)
  • dictionary의 in, 삽입, 조회: O(1)

참고 자료

• https://wiki.python.org/moin/TimeComplexity