백준 10816번. 숫자 카드 2 (Python / 파이썬)

문제

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

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

---

문제 풀이

상근이가 가지고 있는 숫자 카드와 M개의 수가 주어졌을 때

각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지 출력하는 문제이다.

 

즉, M개의 각 수가 몇 개가 있는지 탐색하는 문제이다. 

이때 문제에서 주어진 조건을 보면 숫자 카드의 개수는 최대 500,000이므로 

숫자 카드를 하나하나 확인하면서 개수를 세기에는 너무 많은 시간이 소요된다. 

 

따라서 이분 탐색법을 이용하여 문제를 해결하면 시간을 단축 시킬 수 있다. 

이분 탐색법을 사용할 때 주의할 점은 배열이 정렬되어있어야 한다는 점이다. 

따라서 먼저 입력 받은 숫자 카드를 정렬해주고 

파이썬에서 제공하는 bisect 라이브러리를 이용해 개수를 세어주었다. 

bisect 라이브러리는 bisect_left 와 bisect_right 함수를 제공하는데 

array와 left_value, right_value가 주어졌을 때 이 두 함수를 이용해 

left_value와 right_value 사이의 수의 개수를 구할 수 있다. 

 

예를 들어, 정렬된 배열이 아래와 같이 주어졌을 때

index	0	1	2	3	4	5	6	7	8	9
array	-10	-10	2	3	3	6	7	10	10	10

10이 몇 개인지 구하고 싶다면 left_value = 10, right_value = 10으로 설정하고 

bisect_left, bisect_right 함수를 이용하면 왼쪽에서부터 10의 index를 탐색하고 오른쪽에서부터 10의 index를 탐색해 저장해준다. 따라서 index의 차를 구해주면 배열에서 10의 개수를 구할 수 있다.

---

My Code 

from bisect import bisect_left, bisect_right

# [left_value, right_value]의 개수를 세어주는 함수 
def count_by_range(array, left_value, right_value):
    left_value = bisect_left(array, left_value)    
    right_value = bisect_right(array, right_value)
    
    return right_value - left_value 

n = int(input())
array = list(map(int,input().split()))
array.sort() # 이분 탐색을 이용하기 위해 정렬 

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

for i in target:
    print(count_by_range(array, i, i), end = ' ')