[leetcode #374] Guess Number Higher or Lower

Problem

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 3 possible results:

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

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

Example 4:

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

Constraints:

・ 1 <= n <= 2³¹ - 1
・ 1 <= pick <= n

Idea

Edge case인 것만 조심하면 쉽게 풀 수 있는 문제다. 난이도가 easy인데도 Edge case 생각 안 하다가 두 번이나 틀리니 절망감이 느껴진다 ㅜㅜ

주어진 함수 guess를 활용해서 선택된 수가 무엇인지 추측하면 된다. guess의 결과값이 -1이면 선택된 수가 추측한 값보다 작으며, 1이면 추측한 값보다 크다.

순차적으로 찾으면 Time Limit Exceeded에 걸릴 게 뻔하므로 binary search를 통해 수를 추측하였다. -1이 나올 경우 범위를 [min, pick-1]로 좁히고, 1이 나올 경우 범위를 [pick+1, max]로 좁힌다. 이후 pick은 새로운 범위의 중간값을 선택한다. 이 과정을 계속 반복하면 선택된 수가 어떤 것인지 알 수 있다.

Binary Search를 이용했으므로 Time Complexity는 O(logn)이 나온다.

Solution

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int pick = n/2+1;
        int min = 1;
        int max = n;
        boolean end = false;

        while (!end) {
            switch(guess(pick)) {
                case -1:
                    max = pick-1;
                    pick = min + (pick - min) / 2;
                    break;
                case 1:
                    min = pick+1;
                    pick = pick + (max - pick + 1) / 2;
                    break;
                case 0:
                    end = true;
                    break;
            }
        }

        return pick;
    }
}

Reference

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