리트코드 - 374. Guess Number Higher or Lower

https://leetcode.com/problems/guess-number-higher-or-lower/description/?envType=study-plan-v2&envId=leetcode-75

Guess Number Higher or Lower - LeetCode

사전에 선정된 임의의 숫자(pick)를 맞추는 문제이다.

guess api가 있고, 해당 api에 해당 숫자를 넣으면 pick보다 크거나 작거나 같은지 여부를 반환하는 api이다.

 

최댓값인 n이 주어지므로 이진 탐색을 활용해 문제를 해결할 수 있다.

 

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if num is higher than the picked number
#          1 if num is lower than the picked number
#          otherwise return 0
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l, r = 1, n
        while l <= r:
            mid = (l + r) // 2
            res = guess(mid)
            if res == 1:
                l = mid + 1
            elif res == -1:
                r = mid - 1
            else:
                return mid

 

시작점과 끝점을 정의하고 중간 지점을 정한 다음 반환 여부에 따라 시작점과 끝점, 중간점을 계속 갱신하면서 탐색을 진행할 수 있다.

 

• 시간 복잡도: O(log n). 이진 탐색은 각 단계에서 탐색 범위를 절반으로 줄여나가므로, 최악의 경우에도 log n 
• 공간 복잡도: O(1). 추가적인 공간을 사용하지 않고, 기존의 변수들만으로 탐색을 수행.