BOJ 10826 숫자 카드 2

https://www.acmicpc.net/problem/10826
시간 1초, 메모리 128MB
input :

• N(1 ≤ N ≤ 500,000)
• 숫자 카드에 적혀있는 정수(-10,000,000 <= 정수 <= 10,000,000)
• M(1 ≤ M ≤ 500,000)
• 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수(-10,000,000 <= 정수 <= 10,000,000)

output :

• M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력

조건 :

• 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지

---

bisect 라이브러리를 사용하자.

left_idx = bisect_left(data, item)
right_idx = bisect_right(data, item)

bisect_left 의 경우

from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))

4가 제일 처음 나오는 idx = 2 를 출력하고.

bisect_right 의 경우

from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_right(a, x))

4가 제일 마지막에 나오는 idx + 1 한 숫자를 리턴 한다.

import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
compare = list(map(int, sys.stdin.readline().split()))

data.sort()

for idx, item in enumerate(compare):
    left_idx = bisect_left(data, item)
    right_idx = bisect_right(data, item)
    compare[idx] = right_idx - left_idx

for item in compare:
    print(item, end=" ")