10816번. 숫자카드 2

https://www.acmicpc.net/problem/10816

 

 

참고) 파이썬에서 이 문제를 이분탐색으로 풀면 시간초과가 발생한다.

 

import sys


# 처음으로 key와 같거나 큰 값이 나타나는 위치를 찾는다
def lowerBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            end = mid
        elif nList[mid] < key:
            start = mid + 1
    return end


# 처음으로 key보다 큰 값이 나타나는 위치를 찾는다
def upperBound(start, end, key):
    while start < end:
        mid = (start + end) // 2
        if nList[mid] <= key:
            start = mid + 1
        elif key < nList[mid]:
            end = mid
    return end


n = int(sys.stdin.readline())
nList = list(map(int, sys.stdin.readline().split()))  # 상근이 갖고 있는 카드 리스트
m = int(sys.stdin.readline())
mList = list(map(int, sys.stdin.readline().split()))  # 찾아야 할 카드 리스트
nList.sort()

for i in mList:
    ret = upperBound(0, n, i) - lowerBound(0, n, i)
    print(ret, end=' ')