[백준] 10816 : 숫자 카드 2 python

 

N개의 카드를 오름차순으로 정렬한 리스트 card에서

bisect라이브러리의 내장함수인 bisect_right와 bisect_left를 이용해서 각각의 숫자가 몇개씩 있는지 세고,

딕셔너리에 추가한 뒤 출력하는 방식을 생각했는데 자꾸 시간초과가 나왔다.

 

bisect_right(list, value)는 list에서 value가 들어갈 가장 오른쪽 위치를 알려주고

bisect_left(list, value)는 왼쪽 위치를 알려줘서

정렬된 list에 사용하면 오른쪽위치-왼쪽위치=list내에서 그 숫자의 개수가 된다.

 

그런데 생각해보니 굳이 다시 저장하고 끄집어낼 필요가 없는 거다.

그래서 딕셔너리를 쓰지 않고 그냥 바로 출력해버리니까 정답판정을 받았다.

 

 

import bisect

n = int(input())
card = sorted(map(int,input().split()))
m = int(input())
target = list(map(int, input().split()))

def cnt(arr,value):
    return bisect.bisect_right(arr,value)-bisect.bisect_left(arr,value)

for t in target:
    print(cnt(card,t),end=' ')

 

 

 

아래는 시간초과 받았던 코드들이다

import bisect

n = int(input())
card = list(map(int,input().split()))
m = int(input())
target = list(map(int, input().split()))

card.sort()
d = {}

for t in target:
    if t in card:
        d[t] = bisect.bisect_right(card,t)-bisect.bisect_left(card,t)
    else:
        d[t] = 0

print(' '.join(str(d[t])for t in target))

def bin_search(arr,target,start,end):
    if start>end:
        return 0
    
    mid = (start+end)//2
    if arr[mid]==target:
        return arr[start:end+1].count(target)
    elif arr[mid]>target:
        return bin_search(arr,target,start,mid-1)
    else:
        return bin_search(arr,target,mid+1,end)


for t in target:
    print(bin_search(card,t,0,len(card)-1),end=' ')