[백준] 1920. 수 찾기 : python

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

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을 출력한다.

---

풀이

단순히 숫자를 찾아서 풀면 시간 초과가 난다.

이분 탐색을 사용해서 풀이를 해야한다!

처음에는 파이썬 재귀 초과가 나길래 무슨 문제일까 고민 많이 했는데

binery함수로 재귀 이동할 때 return을 해주지 않으면 계산 후 다시 전 재귀 단계로 돌아오기 때문에,,, return을 필수로 작성해줘야했다.

 

이분탐색법은 미리 입력받은 배열을 정렬한 후 배열의 가운데 숫자와 비교숫자를 비교한 후

입력받은 숫자가 비교 숫자보다 큰 경우 시작점을 가운데 숫자 + 1로

적은경우 끝점을 가운데 숫자 - 1로 바꾸어 계속 비교한다

시간복잡도는 O(logN)으로 중간을 기준으로 탐색을 대상을 절반씩 줄여가서 빠른 편이다!

 

python코드

# 1920 수 찾기
import sys

def binery(i, start, end):
    if start > end:
        return 0
    middle = (start+end)//2
    if i == nArr[middle]:
        return 1

    elif(i < nArr[middle]):
         return binery(i, start, middle - 1)
    else:
        return binery(i, middle + 1, end)


N = int(input())
nArr = list(map(int,sys.stdin.readline().split()))
nArr.sort()

M = int(input())
mArr = list(map(int,sys.stdin.readline().split()))

for i in mArr:
    print(binery(i,0,N-1))