[백준1920번] 수 찾기 / Python3

문제

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안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

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

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

나의 풀이

전형적인 이진 탐색 문제였다. 이진 탐색이란 정렬된 배열에서 중간값을 기준으로 찾으려는 값을 비교하며 작으면 왼쪽절반을 확인하고, 크다면 오론쪽 절반을 확인하면서 값이 있는지 없는지를 탐색하는 방법으로 일반적인 처음부터 끝까지 모든 배열을 탐색하는 방법의 시간복잡도는 O(N)이지만 이진탐색을 절반씩 탐색을 하게되므로 O(logN)이 된다. 따라서 정렬만 되어있다면 기존 탐색보다 시간적으로 효율이 좋다고 할 수 있다.

우선 이 문제를 풀려면 배열을 입력받고 배열을 정렬해주어야 한다. 그래야 찾으려는 값과 중간값을 비교하여 왼쪽으로 갈지 오른쪽으로 갈지를 결정할 수 있기때문이다.

정렬을 하고나서는 이진 탐색을 위한 함수를 만들고 이를 재귀로 돌려야한다. 중간 값과 찾으려는 값이 같으면 True를 반환하고, 아니면 우선 start >= end인지 확인을 하여 start가 같거나 크면 존재하지 않는다는 뜻으로 False를 반환한다. 그렇지 않으면 큰지 작은지를 확인하고 크다면 인자를 start, mid, val을 작다면 mid+1,end,val을 넘겨 재귀를 돌려준다.

코드

# 1920번 수 찾기
import sys

# 이진 탐색
def binSearch(start,end,val):
    mid = (start + end) // 2
    if arr[mid] == val:
        return True
    else:
        if start >= end:
            return False
        if arr[mid] > val:
            return binSearch(start,mid,val)
        else:
            return binSearch(mid+1,end,val)

# main
n = int(sys.stdin.readline())
arr = [int(x) for x in sys.stdin.readline().split()]
arr.sort()

m = int(sys.stdin.readline())
target = [int(x) for x in sys.stdin.readline().split()]

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