🔍 초보자용 가이드 '타겟보다 큰 가장 작은 문자 찾기' - Problem 744 (C++, Python, JavaScript)

Source: Dev.to

문제 요약

주어지는 것:

• letters 라는 정렬된 문자 리스트.
• target 이라는 특정 문자.

목표:

• target 보다 엄격히 큰 가장 작은 문자를 리스트에서 찾는다.
• 그런 문자가 없으면(즉, target 이 모든 요소보다 크거나 같을 경우) 리스트의 첫 번째 문자를 반환한다.

Intuition

Because the array is already sorted, we can avoid a linear scan ( O(n) ) and instead apply binary search ( O(log n) ).

The algorithm follows a “search and discard” approach:

1. Examine the middle element.
2. If letters[mid] > target – this could be the answer. Record the index and continue searching the left half for an even smaller qualifying character.
3. If letters[mid] ≤ target – the middle element and everything to its left are too small. Discard them and search the right half.

If the search finishes without finding a greater character, we “wrap around” and return letters[0].

단계별 설명: 예제 이해

예제 1

letters = ["c", "f", "j"], target = "a"

문자 'a'보다 큰 첫 번째 문자는 'c'입니다.

Result: "c"

예제 2

letters = ["c", "f", "j"], target = "c"

'c'는 허용되지 않습니다. 왜냐하면 우리는 엄격히 더 큰 문자를 필요로 하기 때문입니다. 다음 문자는 'f'입니다.

Result: "f"

예제 3

letters = ["x", "x", "y", "y"], target = "z"

'z'보다 큰 문자가 없습니다; 우리는 처음 요소로 돌아갑니다.

Result: "x"

코드 구현

C++

class Solution {
public:
    char nextGreatestLetter(vector& letters, char target) {
        int n = letters.size();
        int left = 0;
        int right = n - 1;
        int firstTrueIndex = -1;

        while (left  target) {
                firstTrueIndex = mid;
                right = mid - 1;          // look for a smaller qualifying character
            } else {
                left = mid + 1;           // discard left half
            }
        }

        return firstTrueIndex == -1 ? letters[0] : letters[firstTrueIndex];
    }
};

파이썬

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        n = len(letters)
        left, right = 0, n - 1
        first_true_index = -1

        while left  target:
                first_true_index = mid
                right = mid - 1
            else:
                left = mid + 1

        return letters[0] if first_true_index == -1 else letters[first_true_index]

자바스크립트

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
    let left = 0;
    let right = letters.length - 1;
    let firstTrueIndex = -1;

    while (left  target) {
            firstTrueIndex = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return firstTrueIndex === -1 ? letters[0] : letters[firstTrueIndex];
};

핵심 요점

• 이진 탐색 효율성: 매 반복마다 탐색 범위를 절반으로 줄여 O(log n) 시간 복잡도를 달성하고, O(n) 보다 훨씬 빠릅니다.
• Upper Bound 패턴: 이 문제는 전형적인 “upper bound” 탐색으로, 주어진 값보다 엄격히 큰 첫 번째 요소를 찾는 것입니다.
• Wrap‑Around 처리: sentinel 값(예: firstTrueIndex = -1)이나 모듈러 연산을 사용하면 원형 배열 로직을 깔끔하게 구현할 수 있습니다.

최종 생각

이 문제는 검색 기능 최적화에 대한 훌륭한 입문서입니다. 파일 탐색기나 연락처 목록과 같은 실제 시스템에서는 사용자가 문자를 입력할 때 “다음으로 큰” 항목으로 이동해야 하는 경우가 종종 있습니다. 이진 탐색을 마스터하면 최고의 기술 기업에서의 기술 면접 준비는 물론, 수백만 개의 항목까지 확장 가능한 성능 좋은 코드를 작성할 수 있게 됩니다.