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

풀이

• 사실 리스트 안에 문제가 있는지 알면되는거라 선형탐색(for 문 돌리기)을 써도 되겠지만 범위가 10만이라 10만 개 모두 탐색 하기에는 시간이 많이 걸린다고 생각.
• 이럴 때는 이진 탐색을 쓰는 게 맞는 것 같다.
• 리스트에서 주어진 자연수를 이진 탐색으로 찾는다. 있으면 1로 리턴하고, 없으면 0으로 리턴.

코드(572ms)

import sys

ans_n = int(input())
ans_lst = sorted(list(map(int, sys.stdin.readline().split())))

prob_n = int(input())
prob_lst = list(map(int, sys.stdin.readline().split()))

def bi_sec(lst,key) -> int:
    start = 0
    end = len(ans_lst)-1
    while True: # 조건에 맞으면 루프 나가기
        median = (start+end)//2 # 이진탐색을 위한 중앙값 구하기
        if lst[median] == key:
            return 1
        elif lst[median] > key: # 중앙값보다 키 값이 작을 경우
            end = median-1
        else: # 중앙값보다 키 값이 클 경우
            start = median+1

        if start > end: #답이 없어서 교차되면
            return 0
for i in range(prob_n):
    print(bi_sec(ans_lst,prob_lst[i]))