[LeetCode] Guess Number Higher or Lower

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

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 <= 2^31 - 1
1 <= pick <= n

---

숫자 맞추기 게임 문제.

주어진 숫자가 있고, 어떤 함수에 숫자를 넣으면 그 숫자보다 내가 제시한 숫자가 큰지, 작은지, 일치하는지를 리턴한다.

/** 
 * Forward declaration of guess API.
 * @param {number} 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
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let guessWhat = 1;
    let leftHand = 0;
    let rightHand = n;
    let howAboutThis = Math.round(n/2);
    while(guessWhat !== 0){
        guessWhat = guess(howAboutThis);
        if(guessWhat == 0){
            return howAboutThis;   
        }
        if(guessWhat == 1){
            leftHand = howAboutThis;
            howAboutThis = Math.round((howAboutThis + rightHand)/2);
        }
        if(guessWhat == -1){
            rightHand = howAboutThis;
            howAboutThis = Math.round((howAboutThis + leftHand)/2);
        }
    }
};

 

예를 들어 1부터 1,000 까지의 숫자 중에서 50을 찾는다고 했을 때,

우선 500을 넣어 보고, 그 이후로 결과에 따라 최소값과 최대값을 갱신하면서 점차 답을 찾아가는 식으로 풀었다.

문제도 통과됐지만, 런타임이 마음에 들지 않아서ㅋㅋㅋ 주제를 참고해서 정석을 찾아보기로 한다.

그리고 제약조건에 n은 1부터 가능하기 때문에 내가 한 것처럼 leftHand가 0일 필요가 없다.

 

이 문제는 이진 탐색 문제이다.

 

이진 탐색은 간단하게 정렬된 배열에서 원하는 값을 빠르게 찾기 위한 알고리즘이다.

배열의 가운데 값을 구하고, 가운데 값이 찾는 값보다 작은 경우 오른쪽 절반,

큰 경우 왼쪽 절반에서 다시 탐색하는 것을 반복하다 원하는 값을 찾으면 탐색을 종료한다. 심플!

계속 가능성을 절반씩 줄여가며 탐색하기 때문에 효율은 O(log n) 이다.

 

그리고 이 알고리즘에서는 일반적으로 Math.floor를 사용한다.

왜냐하면, 사실상 이번 문제에서 나는 Math.round를 썼으나 사실상 Math.ceil과 마찬가지로 동작하는데...

Math.ceil은 무한 루프나 범위 오류를 일으킬 가능성, 그리고 실수할 가능성이 Math.floor보다 높다.

Math.ceil을 사용할 수 없는 건 아니지만, Math.floor에 비해 안정성이 좀 떨어진다고 볼 수 있다...

 

내가 한 것처럼 마지막으로 비교한 것에서 출발하는 게 아니라 아예 left와 right만 사용해서 답을 찾는다는 차이도 있다.

전통적으로는 left와 right를 갱신하며 계속해서 left와 right의 중간값을 시도하는데,

내가 한 방식은 left/right와 middle의 중간값을 시도하는 방식이었다.

논리적으로 틀린 건 아니지만 동일한 숫자를 반복적으로 비교하게 될 가능성도 있기 때문에 안정성이 떨어진다ㅋㅋ

 

아무튼 이걸 반영해서 다시 깔끔하게 만들어 보면~

var guessNumber = function(n) {
    let left = 1;
    let right = n;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        const result = guess(mid);
        if (result === 0) {
            return mid;
        } else if (result === -1) {
            right = mid - 1; // 이미 탐색한 mid는 제외
        } else {
            left = mid + 1; // 이미 탐색한 mid는 제외
        }
    }
};

 

이렇게 되겠다~