Companies
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num), which returns three possible results:
- -1: Your guess is higher than the number I picked (i.e. num > pick).
- 1: Your guess is lower than the number I picked (i.e. num < pick).
- 0: your guess is equal to the number I picked (i.e. num == pick).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6
Output: 6
Example 2:
Input: n = 1, pick = 1
Output: 1
Example 3:
Input: n = 2, pick = 1
Output: 1
Constraints:
- 1 <= n <= 231 - 1
- 1 <= pick <= n
처음 생각한 것은 간단한 이진탐색이었다.
내가 짠 코드:
public int guessNumber(int n) {
int lo=1, hi=n;
int g = (lo+hi)/2;
int res = guess(g);
while(res != 0){
if(res < 0){
hi = g-1;
}
else{
lo = g+1;
}
g = (lo+hi)/2;
res = guess(g);
}
return g;
}
시간복잡도 O(logN), 공간복잡도 O(1)로 비교적 효율적이라고 생각했는데 TLE가 나왔다.
그래서 삼진탐색을 해야하나 고민하다가 솔루션을 봤는데 역시나 삼진탐색이었다.
아래는 솔루션 코드:
// using ternarySearch
public int guessNumber(int n){
int low = 1, high = n;
while(low <= high){
int mid1 = low+(high-low)/3;
int mid2 = high-(high-low)/3;
int res1 = guess(mid1);
int res2 = guess(mid2);
if(res1 == 0)
return mid1;
if(res2 == 0)
return mid2;
if(res1 < 0)
high = mid1-1;
else if(res2 > 0)
low = mid2+1;
else{
low = mid1+1;
high = mid2-1;
}
}
return -1;
}
배운점:
이진탐색이 TLE가 뜨면 삼진트리를 쓰자..
'Study Log > Algorithm' 카테고리의 다른 글
프로그래머스 / [PCCP 기출문제] 2번 / 석유 시추 (0) | 2024.09.27 |
---|---|
프로그래머스 / 도넛과 막대 그래프 (0) | 2024.09.27 |
잘 까먹는 자료구조들 (0) | 2022.06.03 |
Programmers / Hash - 베스트 앨범 (0) | 2021.08.29 |
Programmers / 정렬 - 가장 큰 수 (0) | 2021.04.18 |
댓글