백준 10816번(숫자 카드2) 파이썬(이분탐색)

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

10816번: 숫자 카드 2

이 문제는 파이썬의 dict 함수(hasp map)를 모른다면 풀 수 없는 문제다.

나 또한 딕셔너리를 생각해내지 못해 막혀서 다른 사람들의 코드를 참고하여 dict 쓰는것을 발견해 풀어 낼 수 있었다.

딕셔너리(hash map) 이란 "key 값": "value 값"의 형태로 키값을 입력하면 밸류 값이 출력되는 형태이다. 

해시의 특성상 검색, 삽입,수정이 빠르기 때문에 이러한 문제 해결에 적합한 데이터 구조이다. 즉 데이터 처리가 빠르다는 장점이 있다는 것이다.

아래는 풀이 코드이다.

import sys
input = sys.stdin.readline

n = int(input())
card1 = sorted(list(map(int,input().split())))
m = int(input())
card2 = list(map(int,input().split()))


dict = {} # 딕셔너리 선언

for i in card1:
    if i in dict: #값이 있을경우 +1을 해준다
        dict[i] +=1
    else: # 없을경우 새로 추가해준다
        dict[i]=1

def bst(array,target,start,end):
    if start>end:
        return 0
    mid = (start+end)//2
    if array[mid] == target: # 값을 찾을 경우 딕셔너리에서 해당 키의 밸류 값을 출력한다
        return dict.get(target)
    elif array[mid] >= target:
        return bst(array,target,start,mid-1)
    else:
        return bst(array,target,mid+1,end)

for i in card2:
    print(bst(card1,i,0,len(card1)-1), end=" ") # 정답 출력

본 코드는 기본적인 이분탐색 지식이 있는 상태에서 보는 걸 추천한다.