[백준][10816] 숫자 카드 2 | 파이썬 | 이진탐색(이분탐색)

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

 

👉구해야 하는 정답

n개의 숫자 카드를 가지고 있습니다.

정수 m개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 몇 개를 가지고 있는지 구하는 문제입니다.

 

👉코드 설계하기

1. 문제의 input을 받습니다.

2. 이진탐색 알고리즘을 사용하여 target값과 같은 수를 카운트 해줍니다.

3. count값을 return해줍니다.

 

👉시도 회차 수정 사항

1. 첫번째 시도 : 시간 초과

실패 원인

    if arr[mid] == target:
            count += 1

 

2. 두번째 시도 : 시간 초과

   if arr[mid] == target:
            return arr.count(target)

위와 같이 수정후 결과물이 제대로 출력 되었지만 시간초과가 나왔다. 

 

시간 초과 코드

import sys

n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
m_list = list(map(int, sys.stdin.readline().split()))

n_list.sort()

def binary_search(target, arr):
    start = 0
    end = len(arr) - 1

    while start <= end: # start가 end를 넘지 않게
        mid = (start + end) // 2
        if arr[mid] == target:
            return arr.count(target)
        elif arr[mid] < target:
            start = mid +1
        else:
            end = mid - 1

for i in m_list:
    result = binary_search(i, n_list)
    if result == None:
        print(0, end =  " ")
    else:
        print(result, end = " ")

 

 

👉정답 코드

import bisect
import sys

# 1. 문제의 input을 받습니다.
N = int(sys.stdin.readline())
arr_n = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
arr_m = list(map(int, sys.stdin.readline().split()))

# 2. 배열 N을 정렬합니다.
arr_n.sort()

# 3. 이분탐색을 활용해 M안의 각각의 원소에 대해 존재하는 개수를 구합니다.
for x in arr_m:
    left = bisect.bisect_left(arr_n, x)
    right = bisect.bisect_right(arr_n, x)
    print(right-left, end=' ')