1920. 수 찾기 (파이썬) | 이분탐색 | 정렬

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

최종 답: 

N = int(input())
arr_A = list(map(int,input().split()))
M = int(input())
arr_B = list(map(int,input().split()))
arr_A.sort()

def binary_search(array,target,start,end):
    while start <= end:
        mid = (start + end)//2

        if array [mid] == target:
            return 1
        elif array [mid] > target:
            end = mid -1
        else:
            start = mid + 1
    return 0

for b in arr_B:
    result = binary_search(arr_A,b,0,N-1)
    print(result)

 

문제풀이:

이 문제를 처음 풀 때는 

 

for b in arr_B:
    if b in arr_A:
        print("1")
    else:
        print("0")

 

이렇게 for문을 이용해서 풀었다. 그런데 "시간초과"가 나면서 오답처리가 되었다. 이 문제는 "이분탐색"이라는 알고리즘을 이용하여 풀어야 하는 문제다. 문제 예시에서는 리스트가 안에 5개 원소밖에 없지만, 만약 수백, 수천개라면 이러한 코드는 비효울적이기 때문이다. 따라서 찾는 횟수를 줄일 수 있는 알고리즘인 이분탐색을 사용해야 한다. 

 

👉 이분탐색이 궁금하다면 먼저 이 글을 보고 오자. 

이진 탐색 & 매개변수 탐색

이분탐색을 알면 쉽게 풀리므로 더 한 설명은 생락한다. 그런데 최종 답 5번째 줄에 arr_A.sort() 가 들어가 있는 이유는 이진탐색은 오름차순이거나 내림차순으로 정렬되어 있을 때만 적용 가능한 알고리즘이므로 넣은 것이다. 

 

* 자제한 코드는 깃허브에 올려두었습니다.