[백준] 10816번 숫자 카드2(with python)

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

10816번: 숫자 카드 2

 

1. 내가 작성한 코드

from collections import Counter

n = int(input())
s_card = list(map(int, input().split()))
s_card1 = sorted(set(s_card))
cnt = Counter(s_card)
m = int(input())
total_card = list(map(int, input().split()))

for i in total_card:
  start = 0
  end = len(s_card1) - 1
  result = False
  while start <= end:
    mid = (start+end)//2
    if s_card1[mid] == i:
      result = True
      break
    elif s_card1[mid] > i:
      end = mid-1
    elif s_card1[mid] < i:
      start = mid+1
  print(cnt[s_card1[mid]] if result else 0, end = ' ')

이분 탐색을 이용해서 풀었는데, count 함수를 쓰니까 시간초과가 발생했다.

 

count 함수를 사용하면 전체 탐색을 해서 시간복잡도가 증가하기 때문인데, 생각해보니 count함수를 쓸 거면 이분 탐색을 할 필요도 없긴 하네

 

 

2. count와 Counter 차이

count()

• 내장함수
• 특정 원소의 개수만을 추출할 때 사용

Counter()

• 외장함수로써, 해당 원소들의 개수를 딕셔너리 형태로 반환
• 딕셔너리에서 원소를 접근할 때 시간 복잡도가 O(1)이기 때문에 높은 성능을 보임