[Baekjoon] 1920번 : 수 찾기 (Python, 이분 탐색)

[Baekjoon] 1920번 : 수 찾기 (Python)

 

목차

 

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

1920번: 수 찾기

Python

 

방법 1 - 메모리 45916KB / 시간 716ms / 코드 길이 515B

 

만약 순차적 탐색을 통해 해당 문제를 풀고자 했다면 시간초과가 나올 것이다.

애초 문제 설정 자체가 이분 탐색을 목적으로 만들어졌기 때문이다.

 

이분 탐색을 통한 조건

1) 찾고자 하는 수(target)가 list에 존재하는지 묻는다.

2) list는 sort를 통해 작은 수부터 큰 수 순서의 오름차순으로 되어있다.

3) target은 반으로 갈라 오른쪽인지 왼쪽인지를 판단한 후 재귀를 통해 값을 찾아 나선다.

 

순차 탐색은 O(N)의 시간복잡도를 가지지만 이분 탐색은 O(logN)의 시간 복잡도를 가진다.

비슷한 탐색 Quick Sort, Heap Sort가 존재

 

def binary_search(arr, target, start, end):
    if start > end:
        return None
    mid = (start+end)//2
    if arr[mid] == target:
        return target
    elif arr[mid] > target:
        return binary_search(arr, target, start, mid-1)
    else:
        return binary_search(arr, target, mid+1, end)

n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
a.sort()
for i in range(m):
    if binary_search(a, b[i], 0, n-1):
        print(1)
    else:
        print(0)

 

방법 2 - 메모리 49576KB / 시간 172ms / 코드 길이 137B

방법 1과 달리 중복되는 값들이 처음에는 존재할 수 있기에 이에 대해서 set으로 값을 단축시킨 후 순차 탐색으로 target이 list에 존재하는지 탐색한다.

 

import sys
input=sys.stdin.readline
input()
a=set(input().split())
input()
for i in input().split():
    print(1) if i in a else print(0)