백준 10816번 숫자 카드 2 파이썬

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

10816번: 숫자 카드 2

 

내 답안

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

N = int(input())
N_list = sorted(list(map(int, input().split())))
M = int(input())
M_list = list(map(int, input().split()))
lst = [0] * M

for i in range(M):
    lst[i] += (bisect_right(N_list, M_list[i]) - bisect_left(N_list, M_list[i]))
    
print(' '.join(list(map(str, lst))))

---

 

Review

 

N 개의 숫자 카드가 들어있는 리스트를 N_list

M 개의 숫자 카드가 들어있는 리스트를 M_list 라고 지정을 해주었다.

숫자카드 1과 비슷한 풀이로는 각 수가 적힌 카드의 개수를 일일히 세주어야 하기때문에 시간초과가 뜰 수 있다.

나는 M_list 를 하나하나 순회 하면서 정렬된 N_list 에 숫자 카드를 세주었다.

왜 정렬을 했냐고 생각한다면 바로 bisect 을 적극적으로 활용하기 위해서 이다.

 

• 짧게 bisect 에 대해 설명을 하자면 이진 탐색을 쉽게 구현하게끔 해주고 인덱스를 반환해 주는 함수다.

      x = [1, 2, 3, 3, 3, 4, 5, 6, 7] 라는 정렬된 리스트가 선언이 되고

      3의 개수를 세고 싶을 때 일일이 하나하나 센다면 O(N)의 시간 복잡도가 걸려서 원소 수가 많을수록 비효율 적이다.

      bisect 라이브러리를 활용하면 시간 복잡도는 O(logN)으로 확 줄일 수 있다.

      1. bisect_left(iterable, r)

      2. bisect_right(iterable, r) 으로 사용할 수 있고

      그림 으로 표현하면

      따라서 인덱스는 각각 bisect_left(x, 3) = 2, bisect_right(x, 3) = 5를 반환해 주고

      bisect_right(x, 3) - bisect_left(x, 3)를 해주면 3이 돼서 3의 개수는 3개가 된다는 걸 알 수 있다.

      bisect 은 원소들이 정렬된 리스트에서 특정 원소의 개수 찾을 때 효과적인걸 알 수 있다.