[LeetCode-374] API 기반 이진 탐색 - 704 템플릿을 그대로 응용하는 법

• 문제 링크: https://leetcode.com/problems/guess-number-higher-or-lower/
• 파일 경로: src/main/java/coding_test/이진탐색/LC0374_GuessNumberHigherOrLower.java
• 난이도: Easy

문제 설명

1~n 사이 숫자 하나(pick)가 미리 정해져 있다. guess(num) API를 호출하면:

• -1: 내가 부른 숫자가 정답보다 큼
• 1: 내가 부른 숫자가 정답보다 작음
• 0: 정답

정답 숫자를 반환해야 한다.

Input: n = 10, pick = 6  -> Output: 6
Input: n = 1, pick = 1   -> Output: 1
Input: n = 2, pick = 1   -> Output: 1

시행착오 — 이번엔 자력으로 풀었다

오늘 처음으로 힌트 없이 완전히 혼자 풀어낸 문제. 278에서 배운 “즉시 리턴 가능한 조건이 있는 경우엔 704 템플릿을 그대로 쓴다”는 감각을 그대로 적용해서, nums[mid] 자리에 guess(mid)의 리턴값을 넣는 방식으로 짰다.

풀고 나서 리뷰받은 개선점:

1. API 호출 중복 — 처음 짠 코드는 if (guess(mid) == 0), else if (guess(mid) == 1)처럼 반복마다 guess()를 최대 2번 호출했다. int result = guess(mid);로 한 번만 호출해서 저장하는 게 맞다 (이 문제도 API 호출을 아끼는 게 중요한 유형).
2. pick은 1 <= pick <= n이라 left를 0이 아니라 1부터 시작해도 됐다.

최종 코드 (자력 구현본)

public int guessNumber(int n) {
    int left = 0;
    int right = n;
    int mid = 0;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (guess(mid) == 0) {
            return mid;
        } else if (guess(mid) == 1) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return mid;
}

변수 추적표 (n = 10, pick = 6)

반복	left	right	mid	guess(mid)	갱신
1	0	10	0+(10-0)/2=5	1 (5<6)	left = 6
2	6	10	6+(10-6)/2=8	-1 (8>6)	right = 7
3	6	7	6+(7-6)/2=6	0 (6==6)	return 6

오늘 배운 내용

이 문제에서 가장 중요한 내용은, 이진 탐색 템플릿에서 “배열 비교”와 “API 호출”이 본질적으로 같은 역할이라는 것이다. nums[mid] == target 자리에 guess(mid) == 0을 넣기만 하면, 704에서 쓴 “즉시 리턴 가능한” 이진 탐색 템플릿을 그대로 재사용할 수 있다. 다만 API처럼 호출 자체에 비용이 있는 경우엔, 한 반복에서 같은 호출을 여러 번 하지 않도록 결과를 변수에 저장해두는 습관이 반드시 따라와야 한다.

오답노트

• 처음 놓쳤던 부분: if (guess(mid) == 0) ... else if (guess(mid) == 1) ...처럼 조건마다 guess()를 다시 호출했다. 로직 자체는 맞지만, 한 반복에 API를 최대 2번 부르는 비효율이 있었다.
• 왜 문제가 되나: 278에서 이미 “API 호출 최소화”가 중요한 조건이라는 걸 배웠는데, 새로운 문제를 풀 때 그 교훈을 바로 적용하지 못했다. 즉 배운 내용을 다음 문제에 자동으로 연결시키는 연습이 더 필요하다는 신호였다.
• 고친 방법: int result = guess(mid);로 결과를 먼저 저장하고, 그 이후 조건문에서는 저장된 result만 비교한다.
• 언제 다시 떠올릴까: 함수 호출이 들어간 조건문을 짤 때는 “이 호출을 몇 번 하고 있는지” 세어보고, 2번 이상이면 변수에 저장하는 방식으로 먼저 리팩터링한다.

꿀팁

• “배열 인덱싱”이 아니라 “함수/API 호출”로 조건을 판단하는 이진 탐색 문제는 생각보다 흔하다 (isBadVersion, guess 등). 템플릿은 똑같이 가져가되, 호출 비용을 항상 의식하자.
• 이전 문제에서 지적받은 개선점을 다음 문제를 풀 때 체크리스트처럼 먼저 떠올려보는 게, 같은 실수를 반복하지 않는 데 효과적이었다.