[binary search / 백준] 10816번 : 숫자 카드 2

- 문제 : https://www.acmicpc.net/problem/10816

 

Silver Lv4 문제이고, 스스로 푼 문제다!

Counter 라이브러리로 쉽게 풀었지만, 풀이 알고리즘에 이분탐색이 있어서 해당 알고리즘을 이용한 풀이도 공부했다. 

참고한 블로그는 여기

 

- 정답 풀이1:

Counter 라이브러리 이용

from collections import Counter

n = int(input())
arr1 = Counter(list(map(int, input().split())))
m = int(input())
arr2 = list(map(int, input().split()))

for i in range(m):
    print(arr1[arr2[i]])

 

- 정답 풀이2:

이분탐색 이용

import sys
input = sys.stdin.readline

n = int(input())
arr1 = sorted(map(int, input().split()))
m = int(input())
arr2 = list(map(int, input().split()))

def binary(n, arr1, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if n == arr1[mid]:
        return arr1[start : end + 1].count(n)
    elif n < arr1[mid]:
        return binary(n, arr1, start, mid - 1)
    else:
        return binary(n, arr1, mid + 1, end)
    
dic = {}
for each in arr1:
    start = 0
    end = len(arr1) - 1
    if each not in dic:
        dic[each] = binary(each, arr1, start, end)
     
print(' '.join(str(dic[x]) if x in dic else '0' for x in arr2))