(Easy - Binary Search) Leetcode - 744. Find Smallest Letter Greater Than Target

오름차순으로 정렬되어 있는 배열에서 target보다 큰 값들 중 가장 작은 값을 찾는 문제입니다.

정렬되어 있는 배열에서 찾는 문제이기에 이진탐색을 사용했습니다.

이진탐색은 정렬된 배열에서 Linear Search보다 빠르게 탐색 가능합니다.

 

target보다 작거나 같으면 찾는 값이 아니므로 제외합니다. 

l = mid + 1;

target보다 크면 정답이 될 수 있는데 그 중 가장 작은 값을 찾는 문제이므로 그 뒤는 제외해주어도 됩니다.

r = mid

이렇게 l과 r의 값이 같아지면 while loop가 종료되고 이 index의 값이 target보다 크면 배열에 있는 target보다 큰 값 중에서 가장 작은 값이 되지만 아니라면 배열에는 target보다 큰 값이 없는 것 입니다. 

    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size() - 1;

        while (l < r) {
            int mid = l + (r - l) / 2;

            cout << letters[mid] << " " << target << " " << l << " " << r  << endl;
            if (letters[mid] <= target) // target보다 작거나 같으면 제외
                l = mid + 1; 
            else {
                r = mid;
            }
        }

        if (letters[r] > target)
            return letters[r];
        return letters[0];
    }

 

 

위의 코드는 좀 더 정리했습니다.

target보다 크다는 의미는 정답이 될 수 있다는 의미이므로 mid index의 값이 target보다 크면 정답으로 임시 저장한 뒤 mid index부터 제외한 뒤 탐색을 계속 이어가는 방식입니다.

    char nextGreatestLetter(vector<char>& letters, char target) {
        int l = 0, r = letters.size() - 1;

        char min = letters[0];
        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (letters[mid] <= target) // target보다 작거나 같으면 제외
                l = mid + 1;
            else { // target보다 크면
                min = letters[mid]; // 정답이 될 수 있으므로 저장
                r = mid - 1;
            }
        }

        return min;
    }