[LeetCode] 374. Guess Number Higher or Lower - Java

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

Guess Number Higher or Lower - LeetCode

---

문제

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

---

풀이

풀이 과정

1부터 n까지의 수에서 선택한 랜덤한 수가 무엇인지 추측하는 문제이다.

하나의 수를 골랐을 때 정답이 맞다면 0, 선택한 수가 정답보다 크다면 -1, 작다면 1을 return 하는 API인 guess함수가 주어진다.

간단하게 이진탐색하여 O(logN)의 시간복잡도로 문제를 해결할 수 있다.

탐색 범위의 시작값과 종료값을 세팅하고 이진탐색을 위한 중간값, 그리고 추측의 결과값을 담을 변수를 선언한다.

int start = 1;
int end = n;
int mid;
int result;

 

범위의 시작값이 종료값보다 커질 때 까지 반복하며 탐색한다.
탐색마다 중간 값은 시작 값에서 탐색범위의 반을 더한만큼으로 설정하고 중간 값으로 정답을 추측한 결과값을 받아온다.
이때 결과값이 정답이라면 중간 값을 바로 return
정답보다 크다면 ( -1 ) 탐색 종료값을 중간값의 -1만큼으로 설정 ( 왼쪽 구역 탐색 )
정답보다 작다면 ( 1 ) 탐색 시작값을 중간값의 +1만큼으로 설정 ( 오른쪽 구역 탐색 )

while(start <= end){
    mid = start + (end - start) / 2;
    result = guess(mid);
    if(result == 0) {
        return mid;
    }
    else if(result < 0){
        end = mid - 1;
    } 
    else {
        start = mid + 1;
    }
}

---

최종 코드

/** 
 * Forward declaration of guess API.
 * @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
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1;
        int end = n;
        int mid;
        int result;

        while(start <= end){
            mid = start + (end - start) / 2;
            result = guess(mid);
            if(result == 0) {
                return mid;
            }
            else if(result < 0){
                end = mid - 1;
            } 
            else {
                start = mid + 1;
            }
        }

        return 0;
    }
}

---