숫자 카드 2
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.
풀이
이 문제는 탐색 배열안에 동일한 숫자가 여러개 존재할 수 있습니다. 이러한 경우 파이썬의 라이브러리인 bisect에서 제공하는 bisect_right, bisect_left 함수를 사용하면 쉽게 갯수를 구할 수 있습니다.
예를 들어, 다음 배열이 존재한다고 하겠습니다.
[1, 2, 3, 4, 4, 4, 5]
해당 배열에서 4를 만약 왼쪽에서 추가하고 싶다면 가장 왼쪽 4에 추가해야겠죠. 이런경우 추가되는 4의 인덱스는 3입니다. 이게 bisect_left 함수입니다. 이경우 bisect_left(arr, 4)로 표현할 수 있습니다.이번에는 오른쪽에서 4를 추가해보겠습니다. 그러면 4가 끝나는 다음 인덱스인 6번 인덱스에 새롭게 4가 추가될겁니다. bisect_right(arr, 4)라고 표현할 수 있습니다. 오른쪽인덱스에서 왼쪽 인덱스 값을 빼준다면 4의 갯수를 알 수 있습니다. 코드를 보겠습니다.
from bisect import bisect_right, bisect_left
import sys
input = sys.stdin.readline
def count_by_range(array, left_value, right_value):
# 오른쪽 인덱스
right_idx = bisect_right(array, right_value)
# 왼쪽 인덱스
left_idx = bisect_left(array, left_value)
# 갯수 반환
return right_idx - left_idx
n = int(input())
# 수행하기 전 미리 정렬함.
card = sorted(list(map(int, input().split())))
m = int(input())
targets = list(map(int, input().split()))
for t in targets:
# 정답 출력
print(count_by_range(card, t, t), end=' ')마찬가지로 해당 함수의 실행 전 꼭 정렬을 해줘야합니다.
