백준 10816 파이썬

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

10816번: 숫자 카드 2

---

코드

n = int(input())
Ncard = sorted(list(map(int,input().split())))
m = int(input())
Mcard = list(map(int,input().split()))

dic_count = {}
for card in Ncard:
    if card in dic_count:
        dic_count[card] += 1
    else:
        dic_count[card] = 1

def binary_search(arr, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if arr[mid] == target:
        return dic_count.get(target) #what??
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, end)
    else:
        return binary_search(arr, target, start, mid - 1)
    

for target in Mcard:
    print(binary_search(Ncard, target, 0, n - 1), end=" ")

처음에는 무지성으로 풀어서 제출했다가 시간 초과가 뜬 경우가 있을 것이다. 이를 해결하기 위해선 이분 탐색 자료구조를 이용해야 한다.

 

풀이

1. 이분 탐색을 위해 Ncard를 sort 해준다.

2. for문 안에서 python의 dictionary를 이용해 Ncard의 카드별 개수를 count 한다.

3. 이분 탐색 함수

    a. start가 end보다 작으면 0을 return 한다.

    b. 중간 길이를 mid라는 변수에 넣어준다.

    c. arr[mid]가 찾는 target이면 target 요소의 개수를 count 한 값을 return 한다.

    d. arr[mid]가 찾는 target보다 작으면 start를 mid + 1 로 바꾼 후 함수를 호출한다.

    e. arr[mid]가 찾는 target보다 크면 end를 mid - 1로 바꾼 후 함수를 호출한다.

4. Mcard에서 for문을 통해 함수를 호출한다.