[LeetCode] 374. Guess Number Higher or Lower

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

Guess Number Higher or Lower - LeetCode

Guess Number Higher or Lower

 

 

누구나 한번쯤은 해보았던 Up/Down 놀이이다.

guess(int n) 함수를 사용하면 추측을 할 수 있는데,

up이면 1, down이면 -1, 맞으면 0을 호출한다.

이를 이용해 정해진 범위(1~n)에서 수를 찾으면 된다.

 

매우매우 간단하다.

다른 알고리즘에서 사용했던 이진 탐색을 쓰도록 하자.

 

한가지 주의점이 있다.

한번에 되겠지하며 submit를 했다가 runtime error가 났는데, 

이유는 n이 int 범위 최대값까지 있으므로,

mid를 구할때 덧셈과정에서 int범위를 넘을 수가 있다.

미리 2로 나눠서 더해주거나, 이 값들을 long으로 받아주자.

(미리 나눌때는 소수점이 버려지는 과정에서 주의하자)

 

전체코드는 아래와 같다.

 

class Solution {
public:
    int guessNumber(int n) {
        long l = 1, r=n, mid=(l+r)/2;
        while(mid>=l) {
            if (guess(mid)==0) return mid;
            if (guess(mid)==1) l = mid+1;
            else r = mid-1;
            mid = (l+r)/2;
        }
        return mid;
    }
};