백준 10816: 숫자카드 2 해설- python

✏️ 문제

10816번: 숫자 카드 2

 

✏️ 풀이

아래는 10815에서 만들어쓴 이진탐색 함수이다.

def BS(array, target, start, end):
  if start > end:
    return 0
  mid=(start+end)//2
  if array[mid]==target:
    return 1
  elif array[mid]>target:
    return BS(array, target, start, mid-1)
  else:
    return BS(array, target, mid+1, end)

10816 에서는 각 수가 적힌 숫자카드가 존재하는지의 유무만이 아니라 그 카드가 몇장있는지를 체크하고 출력한다.

이 문제에 적합한 알고리즘은 Lower Bound와 Upper Bound일 것이다. 각각은 경계값을 찾는것. 즉, 찾고자 하는 수가 처음 나온 위치와 마지막으로 나온 위치를 찾아내므로 이 둘의 차이를 계산하면 그것이 카드의 개수가 될 것이다.

 

(Python 10816)

from bisect import bisect_left, bisect_right

N=int(input())
card=list(map(int,input().split()))
card=sorted(card)
M=int(input())
target_list=list(map(int,input().split()))

answer_sheet=[]
for target in target_list:
  answer=bisect_right(card, target)-bisect_left(card, target)
  answer_sheet.append(answer)

for output in answer_sheet:
  print(output, end=' ')

lower bound와 upper bound는 직접 구현하지 않고 bisect 라이브러리를 이용했다.

lower bound와 upper bound, bisect에 대한 설명은 여기서