백준 1920번 수 찾기 문제 풀이 Python

문제 정의

수 찾기 문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력: 자연수 N, N개의 정수, 자연수 M, M개의 수

출력: 존재하면 1, 존재하지 않으면 0

 

---

문제 해석

문제 자체는 m개의 아이템이 n개 아이템이 있는 배열에 포함되어 있는가? 라는 간단한 문제이나, M과 N의 크기가 커질수록 매우 많은 시간이 소요되어 선형 탐색으로 풀면 시간 초과가 발생함. 따라서 이진 탐색을 통해서 해결한다!

 

---

시간 복잡도

m개의 요소에 대해서 평균적으로 logn 번 탐색하게 되므로 O(mlogn) 으로 추정됨.

---

구현

def binary_search(array, elem):
    pl = 0
    pr = len(array)-1

    while pl <= pr:
        pc = (pl+pr)//2
        if array[pc] == elem:
            return pc
        elif array[pc] > elem:
            pr = pc-1
        elif array[pc] < elem:
            pl = pc+1
    return -1

n = int(input())
a_list = [int(i) for i in input().split(' ')]
m = int(input())
x_list = [int(i) for i in input().split(' ')]

a_list.sort()

for x in x_list:
    if binary_search(a_list, x) == -1: 
        print(0)
    else:
        print(1)

 

• 메모리: 46740 KB
• 시간: 524 ms

 

입력 받은 a 리스트를 정렬한 뒤, 이진 탐색으로 데이터가 포함되어 있는지 검사함