[백준/Python] 1920번 - 수 찾기

 

문제

https://www.acmicpc.net/problem/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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

 

 

출력

 

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

 

 

풀이

 

일일히 for문을 돌려서 탐색하는 것은 시간이 오래 걸리기 때문에 list를 정렬한 다음 절반을 나누어 찾아가는 이분탐색 방법으로 문제를 풀었다.

 

만약 내가 찾는 수가 현재 수보다 작으면 list의 end index를 mid-1로 바꾸고 만약 현재 수보다 크면 list의 start index를 mid+1로 바꿔서 재귀를 돌렸다.

 

 

Code

 

 

import sys
input=sys.stdin.readline
def bi_fin(st,ed,n):
    mid=(st+ed)//2
    n_mid=N_lst[mid]
    if st>ed:
        return 0
    if n_mid==n:
        return 1
    else:
        if n_mid<n:
            return bi_fin(mid+1,ed,n)
        else:
            return bi_fin(st,mid-1,n)

N=int(input())
N_lst=list(map(int,input().split()))
N_lst.sort()
M=int(input())
M_lst=list(map(int,input().split()))
for i in range(M):
    print(bi_fin(0,N-1,M_lst[i]))

 

---

 

EZ~

 

 

1920번: 수 찾기