leetcode 374, Guess Number Higher or Lower[java]

들어가는 말

1부터 n까지의 숫자들 중에 숫자를 하나 선택하고 이를 pick이라고 한다. pick을 모르는 상황에서 pick을 구하는 문제이다. 이때 상속받은 클래스 GuessGame에서 메소드 guess는 들어온 숫자가 pick과 같으면 0을, 보다 작으면 1을, 크면 -1을 반환한다.

코드 설명

이분탐색을 이용해서 간단하게 풀 수 있는 문제였다.

이분탐색이란 어떤 범위의 정렬된(정렬이 되어 있어야 한다) 숫자가 주어질 때, 가운데 숫자를 구해서 가운데 숫자가 찾으려는 숫자보다 작으면 앞의 절반을 버리고 크면 뒤의 숫자를 버리는 방식의 탐색 방법이다.

문제 374는 위의 이분탐색을 이용한다.
먼저 초기에는 왼쪽 같은 1, 오른쪽 값을 n으로 정한다. 가운데 값은 pivot이라는 변수에 저장한다.
pivot은 왼쪽 값 + (오른쪽 값 - 왼쪽 값)/2이다.

그리고 반복문을 실행하는데, pivot 값을 guess에 넣어서 나오는 값을 tmp에 저장한다. tmp에 있는 값이 0이라면 pivot이 pick과 같다는 의미이므로 break한다. 만일 tmp가 -1이라면 pivot이 크다는 뜻이므로 right 변수 값을 조정한다. tmp가 1이 나오면 이는 pivot이 작다는 의미이므로 left값을 조정한다.

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        int pivot;

        while(true){
            pivot = left + (right-left)/2;
            int tmp = guess(pivot);
            if(tmp == 0){
                break;
            }
            if(tmp == -1){
                right = pivot-1;
            }
            if(tmp == 1){
                left = pivot+1;
            }
        }

        return pivot;
    }
}