본문 바로가기
Study Log/Algorithm

LeetCode 374. Guess Number Higher or Lower

by HZie 2022. 11. 16.
Companies

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

  • -1: Your guess is higher than the number I picked (i.e. num > pick).
  • 1: Your guess is lower than the number I picked (i.e. num < pick).
  • 0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

 

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

 

Constraints:

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

처음 생각한 것은 간단한 이진탐색이었다.

내가 짠 코드:

  public int guessNumber(int n) {
      int lo=1, hi=n;
      int g = (lo+hi)/2;
      int res = guess(g);

      while(res != 0){
          if(res < 0){
              hi = g-1;
          }
          else{
              lo = g+1;
          }
          g = (lo+hi)/2;
          res = guess(g);
      }
      return g;
  }

시간복잡도 O(logN), 공간복잡도 O(1)로 비교적 효율적이라고 생각했는데 TLE가 나왔다.

그래서 삼진탐색을 해야하나 고민하다가 솔루션을 봤는데 역시나 삼진탐색이었다.

 

아래는 솔루션 코드:

  // using ternarySearch
  public int guessNumber(int n){
    int low = 1,  high = n;
    while(low <= high){
      int mid1 = low+(high-low)/3;
      int mid2 = high-(high-low)/3;
      int res1 = guess(mid1);
      int res2 = guess(mid2);
      if(res1 == 0)
        return mid1;
      if(res2 == 0)
        return mid2;
      
      if(res1 < 0)
        high = mid1-1;
      else if(res2 > 0)
        low = mid2+1;
      else{
        low = mid1+1;
        high = mid2-1;
      }
    }
    return -1;
  }

 

배운점:

이진탐색이 TLE가 뜨면 삼진트리를 쓰자..

댓글