Leetcode 374. Guess Number Higher or Lower

추측 게임에서 수를 맞추는 문제.

 

1부터 n까지 숫자를 골라 어떤 번호를 골랐는지 맞히는 문제다.
사전 정의된 API intest(int num)를 호출하면 세 가지 가능한 결과가 리턴된다는 말이 있다.

(문제를 풀 때 해당 부분을 인지하면 된다)

-1: 내가 고른 숫자보다 너의 추측이 더 높을 때(= num > pick).
1: 내가 뽑은 숫자보다 추측이 더 낮을 때(= num < pick).
0: 내가 선택한 숫자(즉, num == pick)와 추측이 같을 때.

 

처음엔 인자 n만을 사용해 문제를 해결하고자 했지만 시간 초과로 실패했다.

// 시간 초과된 코드
var guessNumber = function(n) {
    let lower = 1;
    let higher = n;
    
    while(lower <= higher) {
        let guessNum = guess(higher)
        if(guessNum === 0) {
            return n;
        }else if(guessNum === -1){
            n--;
        }else {
            n++;
        }
    }
};

연산에 필요한 시간이 많아진다는 건 지정한 수의 범위가 넓어 그만큼 연산이 이뤄져야 한다는 것이었다.

연산을 줄이기 위해선 수의 범위를 줄여야 했고 lower와 higher의 중간값으로 연산을 진행하며

수의 범위를 좁혀나가는 방식으로 문제를 해결해보기로 했다.

(이 부분은 알고리즘의 개념으로 뭔가 설명이 있을 듯 한데, 알고리즘 용어도 공부를 해야할 필요를 느꼈다.)

 

while문 작동 중간에 선택한 숫자를 맞추면 return으로 빠져나가도록 해줬고

숫자가 맞지 않다면 수의 범위를 계속해서 좁혀나가며 연산이 이뤄질 수 있도록 했다.

/** 
 * 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 lower = 1;
    let higher = n;
    
    while(lower <= higher) {
        let mid = Math.floor((lower+higher)/2);
        let guessNum = guess(mid)
        if(guessNum === 0) {
            return mid;
        }else if(guessNum === -1){
            higher = mid-1;
        }else {
            lower = mid+1;
        }
    }
};