알고리즘 백준 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을 출력한다.

 

 

코드

import sys

def search(numberList,start,end,number):
    while start<=end:  #시작점과 끝점이 만나는지점이 정답일수 있기때문에 둘다 같을 경우까지 #1)
        mid = (start+end)//2 #이분탐색은 중간지점을 정한후 움직여야함 #2)
        if numberList[mid]==number: #타겟(number)가 해당리스트에 있으면 1(true)반환 #3)
            return 1
        elif numberList[mid]<number: #타겟(number)가 해당리스트보다 크면 우측 탐색 #4)
            start = mid+1 #시작점을 우측으로 이동
        else:
            end =mid-1 #끝점을 좌측으로 이동
    return 0  #5)

N = int(input())
nNumber = list(map(int,sys.stdin.readline().split()))
M = int(input())
mNumber = list(map(int,sys.stdin.readline().split()))
nNumber.sort() #정렬
for i in mNumber:
    if search(nNumber,0,N-1,i) ==1:
        print(1)
    else:
        print(0)

 

문제설명

 

0) 문제가 N이 100,000 이하라 했으므로 시간복잡도가 O(N2) 혹은 O(NlogN)이다.

 

0-1) 이분탐색 문제로서 이분탐색은 중간지점(mid)를 정한 후 값이 중간지점보다 크면 우측탐색, 작으면 좌측탐색을 한다(start,end 점을 이용해서)

 

#1) 시작점(start)가 끝점(end)보다 작을 때 까지 코드를 실행한다 -> 이때까지 값을 못찾게 되면 리스트안에 값이 없는것이다

 

#2)이분탐색은 mid(중간지점)을 지정해야 한다

 

#3) 타겟(number)가 리스트의 값과 일치하면 리스트에 있는것이므로 1을 반환한다

 

#4) 타겟(number)가 리스트의mid값보다 크면 우측탐색을 진행하고 시작점을 이동시킨다

      타겟(number)가 리스트의 mid값보다 작으면 좌측탐색을 진행하고 끝점을 이동시킨다

 

#5)타겟(number)가 리스트에 없는 경우 0을 반환한다

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main