[백준알고리즘] 1920번: 수 찾기 -Python

[백준알고리즘] 1920번: 수 찾기 -Python

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

1920번: 수 찾기

이분 탐색 문제로 분류되어 있다. 하지만 딕셔너리를 통해 해시테이블을 이용했다!

import sys

N = map(int, sys.stdin.readline())
keyList = list(map(int, sys.stdin.readline().split()))
pool = {}
for k in keyList:
    pool[k] = 1

M = map(int, sys.stdin.readline())
target = list(map(int, sys.stdin.readline().split()))

for t in target:
    if t in pool:
        sys.stdout.write("1\n")
    else:
        sys.stdout.write("0\n")

추가로 이분탐색으로 풀었던 코드를 추가한다. 이 문제는 딕셔너리로 문제를 푸는 것이 더 빠르게 통과했다.

import sys
input = sys.stdin.readline

def find(start, end):
    mid = (start + end) // 2
    if start >= end: return False
    if a[mid] == t: return True
    elif a[mid] > t:
        return find(start, mid)
    else: # a[mid] < t:
        return find(mid+1, end)

n = int(input())
a = list(map(int, input().split()))
a.sort()
m = int(input())
target = list(map(int, input().split()))

for t in target:
    print(1 if find(0, n) else 0)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다