coding test/leetCode

[leetCode/JS] 374. Guess Number Higher or Lower

쭘봉 2022. 11. 23. 11:25

문제 설명

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

내 솔루션

  • 계속 lower, higher 갱신 해가면서 중간 값으로 재귀를 돌리는 형태로 짬.
  • 풀고나서 조금 다듬고 싶었는데 당이 떨어졌는지 머리가 안굴러갔다.
var guessNumber = function(n) {
  let lower = 0;
  let higher = n;
  const find = (cur) => {
    let isGuess = guess(cur);
    let middle = 0;
    if(isGuess === 0) {
      return cur;
    } else if(isGuess === 1) {
      middle = Math.floor((cur + higher) / 2)
      lower = cur;
    } else {
      middle = Math.floor((lower + cur) / 2)
      higher = cur;
    }
    return find(middle);
  }
  return find(n);
};

 

최고의 솔루션

  • 재가 짠 재귀랑 컨셉, 로직은 같지만 가장 이쁘게 짠 솔루션! 아주 똑똑이다.
  • 대신 guess()를 3번까지 호출 할 수 있겠지만..
var guessNumber = function(n) {
    const findNumber = (start, end) => {
        const mid = Math.floor((end + start)/2);
        if (guess(mid) === 0) return mid;
        if (guess(mid) === -1) return findNumber(start, mid - 1);
        if (guess(mid) === 1) return findNumber(mid + 1, end);
    }
    
    return findNumber(0, n);
};

 

감상평

  • guess() 함수가 -1 리턴하면 내가 고른게 더 크다는 것이 직관적이지 않았다.
  • 차라리 반대로 1 이 크고 -1이 작은거면 좋 았을 것인디!