[10816] 숫자 카드 2

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력
10 (상근이의 숫자 카드의 수)
6 3 2 10 10 10 -10 -10 7 3 (상근이의 숫자 카드의 종류)
8 (예측할 수)
10 9 -5 2 3 4 5 -10 (상근이가 들고 있을거라 예측되는 카드의 종류)

출력
3 0 0 1 2 0 0 2

문제 정리

• 자료 구조, 정렬, 이분 탐색, 해시를 사용한 집합과 맵
  등이 있겠지만 이분 탐색으로 접근하였다.
• 예측 카드 리스트에서 해당 카드를 상근이가 몇 개 들고 있는가를 리턴하는 문제이다.
• python의 bisect를 활용해서 접근

문제 풀이

from bisect import bisect_left, bisect_right

def count_num_bisect(a, x):
    return bisect_right(a,x) - bisect_left(a,x)

n = int(input()) # 상근이의 실제 카드의 수
num_list = list(map(int, input().split())) # 상근이의 실제 카드
num_list.sort() # 정렬 (이분탐색에서 필수조건)
m = int(input()) # 예측 카드의 수
guess = list(map(int, input().split())) # 예측되는 카드

for g in guess:
    print(count_num_bisect(num_list, g), end = ' ')

bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드

bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드

right에서 left를 빼게 되면 a에서의 x의 수가 나오게 된다.