LeetCode 374(Guess Number Higher or Lower, Python)

1. 문제 링크

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

Guess Number Higher or Lower - LeetCode

 

2. 문제 설명

• 1에서 부터 n까지 중 숫자를 하나 pick했을 때, pick한 숫자를 예측하는 Guess Game을 반복한다고 했을 때,
• pick한 숫자를 반환하는 것.
  • 여기서 사전에 정의된 guess(int num)라는 API를 사용하는데,
  • 만약 나의 추측이 실제 pick한 값보다 크면 -1을 반환하고,
  • 실제 pick한 값보다 작으면 1을 반환하고, 
  • 만약 pick한 값과 동일하면 0을 반환한다. 
• 예시1) 예를 들어 n=10이고 pick=6(이건 parameter로 주어지는게 아니다.)이었을 때, guess함수를 호출하면서, pick이 6이라는 것을 판단한 뒤 6을 반환하는 것. 

3. 처음 풀이

• LeetCode 367과 너무 비슷해서, 스킵할까 고민했던 문제. (367번 풀이: https://codingbubu.tistory.com/149) 
• 결국 이것도 그냥 1부터 n까지 for문을 돌리면서, guess(num) == 0일 때를 찾아서 해당 값을 return해도 되겠지만,
  • 이렇게 하면 time complexity가 높아진다. 
• 이전에 풀었던 풀이처럼, binary search를 사용하게 되면, O(logN)만큼의 시간복잡도를 가지게 효율적으로 코드 작성이 가능하다. 
• 여기서도 left, right를 1과 n으로 한 pointer를 두고,
• left <= right일 때까지 while문을 반복하면서,
  • (left+right)//2를 num으로 셋팅한 후,
  • 만약 guess(num) == 0이면 num을 바로 return하고, 
  • guess(num) == -1이 나왔다면, 내가 예측한 숫자가 더 크다는 것이므로, right를 num -1로 이동시킨다.
  • 마찬가지로 guess(num) == 1이 나왔다면, 내가 예측한 숫자가 더 작다는 것이므로, left를 num+1로 이동시킨다.
• runtime이 99.74%로 무난하게 통과하였다.

# 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:
        
        left, right = 1, n 
        
        while left <= right:
            num = (left+right)//2

            if guess(num) == 0:
                return num 
            
            if guess(num) == -1:
                right = num -1 
            
            elif guess(num) == 1:
                left = num +1

4. 다른 풀이

• 거의 대부분이 binary search를 공식처럼.. 하여 풀고 있어서, 다른 풀이가 거의 없었다.