[파이썬] 백준 1920번 문제 풀이 수찾기 (이분 탐색, 이진 탐색)

문제 설명

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

 

문제 링크

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

입출력 예시

프로그램 코드

N = int(input())    #N 입력
num = input().split()   #N개 숫자 입력
li = [] #입력 받은 숫자 리스트에 저장
for i in num:
    li.append(int(i))

li.sort()#이진 탐색을 위한 리스트 정렬

M = int(input()) #M 입력
search = input().split() #찾는 숫자 저장

for i in search: #숫자 하나씩 찾기
    i = int(i) 
    start = 0   #이진탐색 위한 변수 start, end, mid
    end = len(li) - 1
    mid = (start + end) // 2
    flag = 0 #숫자 못 찾으면 0, 찾으면 1 저장
    while start <= end: #이진탐색 반복문
        if i == li[mid]: #숫자 찾기 완료
            flag = 1
            break
        elif i <= li[mid]: #찾는 숫자가 mid보다 작을 때
            end = mid - 1
            mid = (start + end) // 2
        else: #찾는 숫자가 mid보다 클 때
            start = mid + 1
            mid = (start + end) // 2
    print(flag)

 

프로그램 코드 설명

이 문제는 이진 탐색으로 해결하지 않아도 해결은 할 수 있지만 실행시간이 오래 걸려서 백준에서는 틀렸다고 나옵니다.

따라서 이진 탐색을 이용해서 실행시간을 줄여서 문제를 풀어야합니다.

주요 알고리즘만 설명을 드리겠습니다.

 

우선 검색 대상이 되는 값들인 N개의 정수를 입력받아서 li 리스트에 저장을 합니다.

이진 탐색을 위해서는 탐색 대상인 자료구조가 정렬되어 있어야 합니다.

따라서 li 리스트는 정렬해줍니다.

그 후 찾는 숫자 M개를 입력을 받는데 이 숫자들은 하나하나 li 리스트에서 찾아줘야합니다.

찾는 방법은 다음과 같습니다.

start 변수는 현재 찾고있는 리스트의 시작 인덱스입니다.

end 변수는 현재 찾고있는 리스트의 마지막 인덱스입니다.

mid 변수는 현재 찾고있는 리스트의 가운데 인덱스입니다.

1. start = 0, end = 리스트 길이 -1, mid = start 와 end 가운데

2. 찾는 숫자가 mid 에 있는 숫자와 같으면 숫자를 찾았으니 flag 는 1 설정 후 반복문 break

3. 찾는 숫자가 mid 에 있는 숫자보다 작으면 end 를 mid - 1 로 변경 후 mid 재설정

4. 찾는 숫자가 mid 에 있는 숫자보다 크면 start 를 mid + 1 로 변경 후 mid 재설정

5. 이 과정을 탐색할 수 없을 때(start > end)까지 반복