[LeetCode] - 744. Find Smallest Letter Greater Than Target

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Find Smallest Letter Greater Than Target" 문제입니다.

--> https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/

 

문제 : 

You are given an array of characters letters that is sorted in non-decreasing order, and a character target.

There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target.

If such a character does not exist, return the first character in letters.

---

Example 1 :

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

Output : "c"

Explanation : The smallest character that is lexicographically greater than 'a' in letters is 'c'.

 

Example 2 :

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

Output : "f"

Explanation : The smallest character that is lexicographically greater than 'c' in letters is 'f'.

 

Example 3 :

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

Output : "x"

Explanation : There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

 

Constraints :

• 2 <= letters.length <= 104 letters[i] is a lowercase English letter.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.
• target is a lowercase English letter.

---

간략히 설명을 드리자면, 이 문제는 주어진 정렬된 문자 배열 letters와 문자 target이 있을 때, target보다 사전 순서상 큰 가장 작은 문자를 반환하고, 만약 그런 문자가 없다면 배열의 첫 번째 문자를 반환하는 코드를 쓰라는 문제입니다. 위 예시를 보면 바로 이해가 될 겁니다. 바로 제 코드를 보시죠 : 

 

1. 재이의 코드 :

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        for (char letter : letters) {
            if (letter > target) {
                return letter;
            }
        }
        return letters[0];
    }
}

 

제 코드는 되게 무식하게 작동합니다. 문제를 코드언어로 그대로 직역한 느낌입니다. letters에 있는 요소들을 (letter) 반복문을 통해서 하나씩 하나씩 추출해서, 그 letter가 주어진 target 보다 크면, letter를 반환하고, 만약 아니면, target보다 작거나 같은 상황이기 때문에, letters에 있는 가장 작은 요소 (가장 알파벳 순서에서 낮은 / a에 가까운 알파벳)를 반환하는 겁니다. 

---

이 문제가 쉽다고 생각하고 풀고나서 다른 유저들의 답안도 나랑 똑같겠지~하고 훑어봤는데 제 코드 외에도 되게 다양한 방법으로 푸신 분들이 있어서 그분들 코드도 공유해보려고 합니다. 저도 컴공과로서 알고리즘 수업을 들었는데, 이 문제에서 Binary Search를 쓸 생각은 못했습니다. 바로 한 번 코드를 보겠습니다 : 

 

2. Binary Search를 이용한 코드 :

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (letters[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return letters[left % letters.length];
    }
}

 

1. 이진 탐색 초기화:
   • left를 0으로 초기화하고 right를 letters.length로 초기화합니다.
2. 이진 탐색 루프:
   • while (left < right) 루프는 left가 right보다 작을 때 계속 반복합니다.
   • mid를 left와 right의 중간 지점으로 계산합니다.
   • letters[mid]가 target보다 작거나 같으면 left를 mid + 1로 이동합니다.
   • 그렇지 않으면 right를 mid로 이동합니다.
3. 결과 반환:
   • 루프가 종료되면 left는 타겟보다 큰 첫 번째 문자의 인덱스를 가리킵니다. 만약 타겟보다 큰 문자가 배열의 끝을 넘어가면 배열의 첫 번째 문자로 되돌아갑니다.
   • 이를 위해 letters[left % letters.length]를 반환합니다.

이 코드는 시간 복잡도 O(logn)으로 효율적이며, 문제의 요구 사항을 올바르게 처리합니다.

 

---

1,2 코드 순서대로의 Runtime 결과