[백준] 1920번: 수 찾기 (Python/파이썬) + 이진 탐색 (Binary Search)

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을 출력한다.

풀이과정

0. 접근

이중 for 문 또는 in을 사용해서 간단하게 해결할 수 있는 문제지만, 이러한 방법을 사용할 경우 시간 초과 문제가 발생한다. 

따라서 time complexity를 줄일 수 있는 이진 탐색 (binary search)를 통해 문제를 해결한다. 

이중 for문 또는 in을 사용한 경우의 time complexity는 O(NM)이고, 이진 탐색의 경우 O(MlogN)이라는 점에서, 이진 탐색의 time complexity가 더 작다는 것을 알 수 있다. 

 

1. 이중 for 문 사용

import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

for m in M_list:
    chk = False
    
    for n in N_list:
        if m == n:
            print(1)
            chk = True
            break
            
    if chk == False:
        print(0)

 

2. in 사용

import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))

M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

for m in M_list:
    if m in N_list:
        print(1)
    else:
        print(0)

 

3. 이진 탐색 - 시간 초과

import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
N_list.sort()

M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

for m in M_list:
    chk_list = N_list
    while len(chk_list) != 1:
        n = int(len(chk_list)/2)
        if m > chk_list[n]:
            chk_list = chk_list[n:]
        elif m < chk_list[n]:
            chk_list = chk_list[:n]
        else:
            chk_list = chk_list[n:n+1]
    if m == chk_list[0]:
        print(1)
    else:
        print(0)

위 풀이 과정에서 시간 초과가 발생한 근본적인 이유는, 이진 탐색의 종료 조건을 잘못 설정했기 때문이다. 이진 탐색은 정렬된 자료를 반으로 나누어가며 탐색하는 방법이다. 자료를 반으로 나누는 과정에서 인덱스를 활용하는데 (위 풀이 과정에서는 인덱스를 활용하지 않고 직접 리스트를 줄여나갔다), 시작 인덱스과 끝 인덱스를 지정하여 탐색할 자료의 범위를 좁혀간다. 시작 인덱스와 끝 인덱스의 중간인 중간 인덱스의 값이 타겟과 일치하거나, 시작 인덱스가 끝 인덱스보다 커지는 경우 탐색을 종료한다. 

 

4. 이진 탐색 - 정답

import sys

N = int(sys.stdin.readline())
N_list = list(map(int, sys.stdin.readline().split()))
N_list.sort()

M = int(sys.stdin.readline())
M_list = list(map(int, sys.stdin.readline().split()))

for m in M_list:
    left = 0
    right = N - 1

    while left <= right:
        mid = (left + right) // 2
        if m > N_list[mid]:
            left = mid + 1
        elif m < N_list[mid]:
            right = mid - 1
        else:
            left = mid
            right = mid
            break
            
    if left == mid and right == mid:
        print(1)
    else:
        print(0)

인덱스를 활용하여 올바르게 이진 탐색을 구현했다. 

 

cf. 이진 탐색 (Binary Search)

• 이진 탐색
  • time complexity: O(logN)
  • 정렬된 자료를 반씩 나누어 탐색하는 방법
• 구현 개요
  • target: 찾고자 하는 값
  • data: 오름차순으로 정렬된 list
  • start: data의 첫 번째 인덱스
  • end: data의 마지막 인덱스
  • mid: start와 end의 중간값
  • 자료의 중간(mid) 값이 찾고자 하는 값(target)인지 확인
  • 아니라면 자료의 중간(mid)값과 찾고자 하는 값(target)을 비교하여 start, end 이동
• 구현

# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None