[Python] 백준 1920 수찾기

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

 

예제 입력

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

 

예제 출력

1
1
0
0
1

 

코드 및 설명

import sys
n1=sys.stdin.readline()
num1=sorted(map(int,sys.stdin.readline().split()))
n2=sys.stdin.readline()
num2=map(int,sys.stdin.readline().split())

def binary(i,num1,start,end):
    if start>end:
        return 0
    m=(start+end)//2
    if i == num1[m]:
        return 1
    elif i<num1[m]:
        return binary(i,num1,start,m-1)
    else:
        return binary(i,num1,m+1,end)
for i in num2:
    start=0
    end=len(num1)-1
    print(binary(i,num1, start,end))

일단은 이 문제는 단순한 방법으로는 풀면 시간 초과가 뜬다.

import sys로 입력 시간을 단축시켜도 마찬가지이다.

 

이 문제는 알고리즘 분류에서도 볼 수 있듯이 이분탐색으로 풀어야 한다.

특정 지점에서 해당 숫자가 큰지 작은지 분석해 탐색시간을 절반씩 줄여주는 방식이다.

이를 위해 나중에 검색해야 할 숫자는 정렬로 처리를 해주었다.

 

메인에서는 특정 숫자가 있는지 해주어야 하므로 반복문안에서 함수 호출하는 방식을 이용해주었다.

 

함수를 뜯어보자

 

일단 함수에서는 특정 숫자와 찾아봐야 하는 리스트, 시작점과 끝점이 필요하다.

모든 것을 탐색하면 오래 걸리기에 그 시간을 줄여주기 위한 작업이다.

만약 시작점이 끝점보다 크게되면 오류이므로 return 0으로 마무리를 해주어야 한다.

그리고 위치를 가운대로 맞춰준다. 여기서는 알려주는 것이 m이라는 변수이다.

 

만약 리스트 특정위치의 숫자가 찾고자 하는 숫자가 같으면 있다는 의미인 1을 반환해준다.

아니면 그 숫자가 해당 위치의 숫자보다 작으면 이제 가운데를 기준으로 앞에를 다시 호출해 비교를 해준다.

그외의 경우면 이제 가운데를 기준으로 뒷부분을 처리해주어야 한다.

가운데란 start와 end점의 가운데(중간)를 의미한다.

 

이런 방식으로 호출을 통해 반환하면 시간도 줄어들면서 빠르게 탐색이 가능하다.