백준 1920번 수 찾기 파이썬

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

1920번: 수 찾기

이 문제는 시간제한이 1000ms이기 때문에 시간 복잡도를 잘 활용해야 한다.

문제를 보자마자 이진 탐색이라는 걸 알았지만 혹시 몰라서 간단하게 코딩을 했었다.

N = int(input())
NA = list(map(int, input().split()))
M = int(input())
MA = list(map(int, input().split()))
for i in MA:
    if i in NA:
        print(1)
    else:
        print(0)

이거는 당연히 시간복잡도가 길어 실패한 코드 이다.

.

.

이제 이진 탐색으로 접근해 보자.

이진 탐색을 모른다면 참고만 하자!

https://thingjin.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%ED%8C%8C%EC%9D%B4%EC%8D%AC

 

 

- 반복문

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return 1 # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None


N = input()
NA = sorted(list(map(int, input().split())))
M = input()
MA = list(map(int, input().split()))
for i in MA:
    if binary_search(i,NA):
        print(1)
    else:
        print(0)

이진 탐색을 반복문으로 해결하는 코드를 짰다.

 

.

.

혹시 몰라 재귀 함수로도 해결하는 코드도 짜보았다.

 

- 재귀

def binary_search(target, data, start, end):
     if start > end: # 찾는 값이 없을 때
        return None
    
     mid = (start + end) // 2
    
     if target == data[mid]:
         return data[mid]
     elif data[mid] < target : # 왼쪽 구간에 대해 재귀 호출
         return binary_search(target, data, mid + 1, end)
     else:                     # 오른쪽 구간에 대해 재귀 호출
         return binary_search(target, data, start, mid - 1)

N = input()
NA = sorted(list(map(int, input().split())))
M = input()
MA = list(map(int, input().split()))
start = 0
end = len(NA) - 1
for i in MA:
    if binary_search(i, NA, start, end):
        print(1)
    else:
        print(0)

(사실 파이썬에서는 N과 M은 필요 없는 코드이다...)