문제 소개
숫자 추측 게임(Guess Game)을 한 번쯤 해본 적이 있을 것입니다. 이 게임의 규칙은 다음과 같습니다.
플레이어 1이 1부터 n 사이의 숫자 하나를 정합니다. 플레이어 2는 그 숫자가 무엇인지 맞춰야 하며, 틀릴 때마다 플레이어 1은 정답이 자신이 고른 숫자보다 높은지 낮은지 알려줍니다.
이를 위해 guess(num) 함수를 사용할 수 있으며, 이 함수는 다음 세 가지 결과 중 하나를 반환합니다.
- -1: 플레이어 1의 숫자가 추측한 값보다 낮음
- 1: 플레이어 1의 숫자가 추측한 값보다 높음
- 0: 숫자를 정확히 맞춤
예를 들어 입력이 n = 10, pick = 5라면 출력은 5가 됩니다.
접근 방법: 이진 탐색
매번 순서대로 하나씩 확인하는 대신, 이진 탐색(Binary Search)을 활용하면 시간 복잡도 O(log n)만에 답을 찾을 수 있습니다. 단계별 풀이 과정은 다음과 같습니다.
- 탐색 범위를 l = 1, r = n으로 초기화합니다.
- l <= r인 동안 아래 과정을 반복합니다.
- 중간값 m = l + (r - l) / 2를 계산합니다.
- guess(m)이 0이라면 m이 정답이므로 m을 반환합니다.
- guess(m)이 -1이라면 정답이 더 낮으므로 r = m - 1로 범위를 줄입니다.
- 그 외의 경우(정답이 더 높음)에는 l = m + 1로 범위를 올립니다.
- 반복문이 끝나면 0을 반환합니다(정답을 못 찾은 경우).
C++ 코드 예제
아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int number;
int guess(int num){
if(number > num)
return 1;
if(number < num)
return -1;
return 0;
}
public:
Solution(int n){
number = n;
}
int guessNumber(int n) {
int l=1,r=n,m;
while(l<=r){
m=l+(r-l)/2;
if(guess(m)==0)
return m;
if(guess(m)==-1)
r=m-1;
else
l=m+1;
}
return 0;
}
};
main(){
Solution ob(5); //pick = 5
cout << (ob.guessNumber(10));
}입력
5,10
출력
5
코드 설명
Solution 클래스 내부에는 실제 정답 숫자를 저장하는 number 변수와, 추측값을 비교해 -1, 1, 0 중 하나를 반환하는 guess() 함수가 있습니다. guessNumber() 함수는 위에서 설명한 이진 탐색 로직을 그대로 구현한 것으로, 매 반복마다 탐색 범위를 절반씩 줄여가며 정답을 찾습니다.
이 방식은 최악의 경우에도 약 log₂(n)번의 추측 만에 정답을 보장하므로, n이 클수록 선형 탐색 대비 압도적으로 효율적입니다.