파이썬 Collection과 bisect 라이브러리

여느때와 다름 없이 1일 1백준을 목표로 백준을 풀던 중

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

해당 문제를 풀며 시간초과를 맞닥뜨리게 되었다.

n = int(input())
numbers = list(map(int, input().split()))
count = {}
for i in range(n):
    count[numbers[i]] = numbers.count(numbers[i])

m = int(input())
numbers = list(map(int, input().split()))
answer = []
for i in range(m):
    if numbers[i] in count.keys():
        answer.append(count[numbers[i]])
    else:
        answer.append(0)

for elem in answer:
    print(elem, end=' ')

이렇게 코드를 짰는데, 시간초과가 나온 지점에 대해서 생각해보면

for i in range(n):
	count[numbers[i]] = numbers.count(numbers[i])

이 부분이다. 여기서 리스트의 count()는 시간복잡도가 O(n)이라서 저 코드는 n^2이 된다. 코테에서 브루트 포스문제도 아닌데 n^2이다? 이건 안된다.

for i in range(m): 
	if numbers[i] in count.keys() :

여기도 우려되는 부분이기는 하다 keys()가 반환하는 것이 리스트이기 때문에 여기도 n^2이라고 보이기 때문이다.

그래서...이것저것 알아보던 중...라이브러리에 대해서 발견했다.

• Counter라이브러리: from collections import Counter 이렇게 불러올 수 있다.
• Bisect 라이브러리: from bisect import bisect_left, bisect_right 이렇게 불러올 수 있다.
  Counter 라이브러리는 원소의 개수를 세서 딕셔너리로 반환하는 라이브러리다.
  Bisect는 이진탐색을 지원해주는 라이브러리이다.

Counter 라이브러리를 통해서 시간복잡도를 O(n)으로 줄일 수 있었다.
Bisect의 경우 직접 구현해보다가, 어떻게 하면 좀 더 편하게 작성할 수 있을까 하고 검색해봤는데 있다고 하길래 써봤다, 범위를 조정하여서 각각 원소의 개수를 셀 수 있는데, 이번 코테문제에서 적용하지는 않았지만 진짜 엄청난 개꿀 라이브러리 같다.

• dictionary의 get 메소드: 이것도 진짜 꿀인 것 같다. 매개변수가 하나가 있으면 그 매개변수가 있는지 없는지를 파악해주고, 두 개 넣으면(예를 들어 get(1, 0)) 왼쪽에 있는 값이 없으면 오른쪽에 있는 값을 리턴해준다.
  이 무슨 말도 안되는 엄청나게 편리한 메서드인지.... 열심히 외우고 연마해야겠다고 생각했다.

마지막으로 코드를 올리며 마칩니다...빠이루

from bisect import bisect_left, bisect_right
from collections import Counter

def count_by_range(array, left, right):
    right_index = bisect_right(array, right)
    left_index = bisect_left(array, left)
    return right_index - left_index

n = int(input())
numbers = list(map(int, input().split()))
# Counter를 사용하여 각 숫자의 개수를 미리 계산
count = Counter(numbers)

m = int(input())
ans_numbers = list(map(int, input().split()))w
for i in range(m):
    # ans_numbers의 각 요소가 count 딕셔너리에 있는지 확인하고, 있으면 해당 값을 가져옴
    ans_numbers[i] = count.get(ans_numbers[i], 0)

for elem in ans_numbers:
    print(elem, end=' ')