백준 1920: 수 찾기 (파이썬)

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

1300번: K번째 수

---

코드

#https://teching.tistory.com/
import sys


def find(a, list):
    left = 0
    right = len(list)
    while left < right:
        mid = (left + right) // 2
        if list[mid] > a:
            right = mid
        elif list[mid] < a:
            left = mid + 1
        else:
            return 1
    return 0


n = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline().rstrip())
needs = list(map(int, sys.stdin.readline().split()))
nums.sort()

for i in needs:
    print(find(i,nums))

해설

어떤 수가 해당 배열에 존재하는지 찾는 문제이다.

기본적인 방법으로는 for문을 이용해서 전부 다 찾는 방법이 있겠지만 해당 방법의 경우 하나의 수를 찾는 게 배열의 개수가 N이라면 O(N)으로 M개의 숫자를 찾기 위해서는 O(N*M)이 걸리게 된다.

즉 최악의 경우에는 N과 M값이 100,000이 오므로 시간 초과가 발생한다.

 

시간을 줄이기 위해서 사용한 방법이 바로 이분 탐색이다.

이분 탐색에 간단하게 설명하자면 배열을 정렬한 뒤에 중간값을 확인하고 높으면 오른쪽 부분을 낮으면 왼쪽 부분을 다시 탐색한다. 해당 방법을 반복해 나가면 배열에 해당 값이 있는지 찾을 수 있다.

시간 복잡도는 $log_2 {N}$ 이 걸리게 된다.

 

예를 들어 0~10이 있는 배열에서 9 값을 찾는다고 생각하면

1.  [0 1 2 3 4 5 6 7 8 9 10]에서 중간값인 5랑 목표 값인 9을 비교한다. 
    목표 값이 더 크기 때문에 5를 기준으로 오른쪽 부분 배열로 다시 탐색을 한다.
2. [6 7 8 9 10]에서 중간 값은 8, 목표 값 9가 더 크기 때문에 8을 기준으로 오른쪽 부분의 배열로 다시 탐색한다.
3. [9 10]에서 중간 값은 9이다.((9+10)//2=9) 따라서 목표 값이 있음을 확인할 수 있다.

for으로는 9번을 수행해야 하지만 이분 탐색으로는 3번만 수행하면 찾을 수 있다는 것을 확인할 수 있다.