[파이썬] 백준 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을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

1
1
0
0
1

- 첫번째 방법 : 이진 탐색으로 탐색

# 이진 탐색
def binary_search(value,start,end):
    median=(start+end)//2
    if start>end:
        return False
    if n_list[median]>value: # 중앙값이 value보다 크면 end를 median-1로 해서 다시 서치
        return binary_search(value,start,median-1)
    elif n_list[median]<value: # 중앙값이 value보다 작으면 start를 median+1로 해서 다시 서치
        return binary_search(value,median+1,end)
    else: # 중앙값이 value와 같은경우 존재하는 것이므로 true
        return True
  
n=int(input())
n_list=list(map(int,input().split()))
m=int(input())
m_list=list(map(int,input().split()))
n_list.sort() # 이진탐색을 위해 오름차순 정렬
for i in m_list:
    if binary_search(i,0,n-1):
        print(1)
    else:
        print(0)

- 두번째 방법: set을 이용하여 빠르게 탐색

n=int(input())
# set 형태로 담음({3,5,7}) -> 특정한 원소가 포함되어있는지를 간단하고 빠르게 확인가능
arr=set(map(int,input().split())) 
m=int(input())
x=list(map(int,input().split()))

for i in x:
    if i not in arr:
        print('0')
    else:
        print('1')