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

import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
Narr = list(map(int, input().split()))
Narr.sort()

M = int(input())
Marr = list(map(int, input().split()))
isTrue = False

# Counter를 사용하여 각 요소의 개수를 미리 셈
count_dict = Counter(Narr)
countArr = [0] * M

for i in range(M):
  pl = 0
  pr = N - 1

  while(pl <= pr):  
    pc = (pl + pr) // 2

    if (Marr[i] == Narr[pc]):
      countArr[i] = count_dict[Marr[i]]
      break
    elif (Marr[i] < Narr[pc]):
      pr = pc - 1
    else:
      pl = pc + 1

print(" ".join(map(str, countArr)))

바로 이전 포스팅 수 찾기와 비슷하게 이진탐색을 활용해서 풀었다.

그 전과 다른 점은 각 수가 적힌 카드의 개수를 세는 것이었는데 처음에 count 함수로 풀었더니 시간초과가 났다. ..

시간 초과 문제가 발생하는 이유는 배열을 정렬한 후, 이진 탐색을 사용하여 값을 찾고, 다시 해당 값을 count 메소드를 사용하여 세는 과정이 비효율적이기 때문입니다. 이 방식은 큰 데이터셋에서 비효율적일 수 있습니다. - gpt의 답변 ...

countArr[i] = Narr.count(Narr[pc])

if문 안에서 값을 찾은 후 count 메소드를 사용하였는데 이게 비효율적이라고 한다.

---

그래서 Counter 함수를 이용해서 각 요소의 개수를 미리 계산해두고,

 값을 찾았다면 count_dict 에서 해당 값의 요소 개수를 바로 가져와 사용할 수 있도록 했다.

 

그리고 countArr가 배열 형태로 출력되므로 join을 활용해서 문자열처럼 출력되도록 한다.

알록달록한 결과 .. ㅎㅎ