(C++) - LeetCode (easy) 374. Guess Number Higher or Lower

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

Guess Number Higher or Lower - LeetCode

이분탐색 문제였습니다.

📕 풀이방법

📔 풀이과정

1. 1초는 1억연산이므로 n이 2^31승인 경우 O(n) 인 시간복잡도를 가지는 brute force로 해결할 수 없습니다. O(logn)인 이분탐색을 사용해야합니다.

2. 1 ~ n-1까지의 범위를 이분탐색해 값을 구합니다. 값이 없는 경우는 없으므로 3가지 조건을 고려해 수행합니다.

  2-1. res == -1인 경우 pick한 값 mid가 정답보다 작으므로 mid+1 ~ n-1 범위에 정답이 있습니다.

  2-2. res == 1인 경우 pick한 값 mid가 정답보다 크므로 1 ~ mid-1 범위에 정답이 있습니다.

  2-3. 나머지 경우는 답을 찾은 경우이므로 정답을 반환해줍니다.

3. 이분탐색을 했음에도 값이 return되지 않았다면 정답은 n이므로 이를 반환합니다.

---

📕 Code

📔 C++

#include <bits/stdc++.h>
#define ll long long
/** 
 * 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);
 */

class Solution {
public:
    int guessNumber(int n) {
        ll l = 1;
        ll r = n-1;
        while(l<=r){
            ll mid = (l+r)/2;
            int res = guess(mid);
            if(res == -1) r = mid - 1;
            else if(res == 1) l = mid + 1;
            else return mid;
        }
        return n;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.