[백준] 1920번 - 수 찾기

문제 링크 : www.acmicpc.net/problem/1920

1920번: 수 찾기

단순 탐색 문제로, 처음에는 이진탐색을 이용해서 풀었다.

import sys

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (high+low)//2

        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1

    return -1


N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().rstrip().split(' ')))
arr.sort()
M = int(sys.stdin.readline())
targets = list(map(int, sys.stdin.readline().rstrip().split(' ')))

for target in targets:
    if binary_search(arr, target) == -1:
        print('0')
    else:
        print('1')

제출 후에 다른 분들의 코드를 살펴보니 수행시간이 유독 짧은 코드들이 있었는데, 이진 탐색이 아니라 set을 이용한 풀이가 있었다. set을 이용한 코드는 다음과 같다.

import sys

N = int(sys.stdin.readline())
arr = set(sys.stdin.readline().split())
M = int(sys.stdin.readline())
targets = sys.stdin.readline().split()

for target in targets:
    if target in arr:
        print('1')
    else:
        print('0')

두 번째 코드가 첫 번째 코드보다 약 4배정도 빨랐다.