374. Guess Number Higher or Lower

24.12.08

• 문제를 이해해보자. 1~n까지의 숫자 중 하나를 맞추면되는데, up down게임처럼 큰지 작은지만 말할 것이다. 그 역활을 int guessNumber()함수의 반환값을 통해 알려줄건데 -1, 0, +1값으로 알려줄 것이다. 추측한 값을 맞추어라.

차피 조만간 BS문제가 나올 것 같으니 정석적으로 코드를 작성해서 해결해보자.

/** 
 * 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 binary_search(int mid, int start, int end){;
        switch(guess(mid)){
            case -1:
                return binary_search((start+mid-1)/2, start, mid-1);

            case 0:
                break;

            case 1:
                return binary_search((mid+1+end)/2, mid+1, end);

        }
        return mid;
    }
    public int guessNumber(int n) {
        return binary_search(n/2, 0, n);
    }
}

StackOverflowError가 발생하여 while형식으로 바꾸어보았다.

/** 
 * 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 mid=n/2, start=0, end=n, guess_var=guess(mid);

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

TLE가 발생하였다. TLE가 발생할 만한 코드는 아닌 듯 한데.. 예외상황으로 생각해 볼 수 있는 것은 mid가 0이 되어버리는 것이다. sout을 추가해보자.

오버플로우가 발생하는 듯 하다. 문제 조건을 확인해보니 n의 최댓값이 2^31-1로 32비트, 4바이트의 크기를 가진다. int가 4byte인데 양의 범위니 unsigned int를 사용해보..면 되지만 자바엔 unsigned가 없으니 Long으로 하자.