10816: 숫자 카드 2 - Python

beaver.zip·2024년 12월 12일

[알고리즘] 백준

목록 보기

32/45

문제

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)