[Leetcode] Guess Number Higher or Lower

문제 출처

• https://leetcode.com/problems/guess-number-higher-or-lower/

Guess Number Higher or Lower - LeetCode

 

 

문제 해설

• 1부터 n까지 숫자들을 주어질 때, guess 함수를 이용해 찾고자 하는 숫자(pick)가 무엇인지 찾는 문제
•  guess 함수는 이미 정의되어 있고, 숫자를 입력하면 -1, 0, 1 중 하나의 결괏값을 반환
  • -1: 함수에 입력한 값이 pick보다 큰 경우
  • 0: 함수에 입력한 값이 pick이랑 같은 경우
  • 1: 함수에 입력한 값이 pick보다 작은 경우

 

문제 풀이

# source: https://leetcode.com/problems/guess-number-higher-or-lower/

# def guess(num: int) -> int:


class Solution:
    def guessNumber(self, n: int) -> int:
        start = 1
        end = n

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

            res = guess(mid)

            if res == 0:
                return mid
            elif res == -1:
                end = mid - 1
            elif res == 1:
                start = mid + 1

 

 

• 1부터 n까지 탐색하는데 시간복잡도가 O(logN)인 이진 탐색을 이용

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/leetcode/guess_number_higher_or_lower.py