[LeetCode] 744. Find Smallest Letter Greater Than Target

LeetCode - 744. Find Smallest Letter Greater Than Target 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/find-smallest-letter-greater-than-target/

풀이

letters 벡터에서 target 보다 큰 알파벳 중 가장 작은 알파벳을 출력한다.

target 보다 큰 알파벳이 없다면 letters에서 가장 작은 알파벳을 출력한다.

lower_bound를 구현하여 해결할 수 있다.

lower_bound 란 ?

Binary Search에 기반한 탐색 방법으로, 찾으려 하는 key 값이 없으면 key 값보다 큰 가장 작은 값을 찾는다.

같은 원소가 여러 개 있어도 상관없으며 항상 유일한 해를 구할 수 있다.

소스 코드

class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        
        if (letters.back() <= target) {
            return letters[0];
        }
        
        int left = 0, right = static_cast<int>(letters.size());
        while (left <= right) {
            int m = (left + right) >> 1;
            if (letters[m] <= target) {
                left = m + 1;
            }
            else {
                right = m - 1;
            }
        }
        return letters[left];
    }
};