[백준] 파이썬 10816 : 숫자 카드 2

 

 

 

# 이진탐색 사용해서 풀기
N = int(input()) # 숫자 카드 개수
cards = sorted(list(map(int, input().split()))) # 숫자 카드 리스트
M = int(input()) # 찾아야할 숫자 개수
nums = list(map(int, input().split())) # 찾아야할 숫자 리스트

num_dict = {} 
for n in cards: # 갖고 있는 카드들을 딕셔너리에 추가. 리스트에 있는 개수만큼 value를 더한다.
    if n in num_dict:
        num_dict[n] += 1
    else:
        num_dict[n] = 1

# 이진탐색 함수 
def binary(target, cards, start, end):
    if start > end: # 시작값이 끝값보다 크면 찾을수없으니 0 리턴
        return 0

    mid = (start + end) // 2 # 중간값을 구함

    if target == cards[mid]: # 찾는값이 중간값과 일치하면 해당 값을 리턴 
        return num_dict[target]
    elif target < cards[mid]: # 찾는값이 중간값보다 작으면 시작부터 중간-1로 범위를 좁힘
        return binary(target, cards, start, mid - 1)
    else: # 찾는 값이 중간값보다 크면 중간+1부터 끝값으로 범위를 좁힘
        return binary(target, cards, mid + 1, end)

# 찾아야할 숫자 리스트만큼 반복 
for num in nums:
    print(binary(num, cards, 0, len(cards) - 1), end=' ')

 

 

 

# dictionary 사용해서 풀기
N = int(input()) # 숫자 카드 개수
cards = sorted(list(map(int, input().split()))) # 숫자 카드 리스트
M = int(input()) # 찾아야할 숫자 개수
nums = list(map(int, input().split())) # 찾아야할 숫자 리스트

num_dict = {} 
for n in cards: # 갖고 있는 카드들을 딕셔너리에 추가. 리스트에 있는 개수만큼 value를 더한다.
    if n in num_dict:
        num_dict[n] += 1
    else:
        num_dict[n] = 1

for i in nums: # 찾아야할 숫자들만큼 반복 
    if i in num_dict: # 찾아야할 숫자가 딕셔너리에 있다면 해당 개수 출력
        print(num_dict[i], end=' ')
    else:
        print(0, end=' ')

 

 

처음에는 딕셔너리를 이용해서 푼 문제였다. 나중에 알고리즘 분류를 보고 또 다른 블로그들을 찾아보니 이진탐색으로도 풀 수 있어서 재귀함수를 사용해 이진탐색 풀이도 구현해보았다.

 

 

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

10816번: 숫자 카드 2