[프로그래머스] 수 찾기

아이디어 도출 방법

주어진 문제는 search배열(n)에서 특정 숫자(m)를 찾는 문제였다. 하지만 배열의 길이가 크고, 찾고자 하는 특정 숫자가 많아지면 이중반복문으로는 해결하기 어렵다.

 

따라서 이중 반복문을 제거하고, 주어진 배열에서 더 빠르게 탐색할 수 있는 알고리즘이 필요한데 이것이 이분 탐색이다.

이분 탐색은 기존의 O(n)의 시간 복잡도를 O(logn)으로 줄여준다.  이런 방법을 사용한다면 기존의 O(n*n)의 시간 복잡도에서 O(nlogn) + O(mlogn)으로 개선할 수 있다.

 

또한 이분 탐색을 하기 전 필수적으로 수행되어야 할 것은 '특정 배열'(주어진 숫자를 찾고자 하는 배열)이 정렬되어 있어야 한다.

 

최종 결과

n = int(input())
search = list(map(int, input().split()))

m = int(input())
arr = list(map(int, input().split()))

#필수조건 찾고자 하는 필드는 항상 오름차순으로 정렬됨
search.sort()

for target in arr:
    lo = -1
    hi = n-1

    """반복문 불변식1 lo < hi
       반분문 불변식2 a[lo] < x <= a[hi]
    """

    #for문을 탈출하면 lo + 1 = hi가 됨 (즉 lo hi)이 상태임
    #반복문 불면식이 성립한다.
    while lo + 1 < hi:
        mid = int((lo + hi) / 2)
        
        if search[mid] < target:
            lo = mid
        else:
            hi = mid

    if search[hi] == target:
        print(1)
    else:
        print(0)

 

후기

오랫만에 이분탐색 문제를 풀어보았고, 실력을 더 올리기 위해 프로그램에 증명을 도입해봤다.

 

한가지 재미난 점은 set을 이용해 푼 후기가 있었다. set은 시간 복잡도가 O(1)인데 어떻게 구현됐는지 나중에 블로그에 글을 남겨야겠다(https://bjwan-career.tistory.com/53)