Python에서 타겟보다 큰 가장 작은 문자 찾기 – 이진 탐색 완벽 가이드

문제 설명

정렬된 소문자 문자 리스트 letters와 타겟 문자 t가 주어졌을 때, 리스트에 있는 요소 중 타겟보다 큰 값들 중에서 가장 작은 문자를 찾는 문제입니다.

여기서 중요한 포인트는 문자가 순환(wrap around)한다는 점입니다. 즉, 타겟이 'z'이고 letters = ['a', 'b']라면, 리스트의 끝에 도달하면 다시 처음으로 돌아가므로 답은 'a'가 됩니다.

예시

입력이 ["c", "f", "j"]이고 타겟이 'a'라면, 'a'보다 큰 문자 중 가장 작은 것은 'c'이므로 출력은 'c'가 됩니다.

접근 방법: 이진 탐색

리스트가 이미 정렬되어 있으므로 이진 탐색(Binary Search)을 활용하면 O(log n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

• l을 0으로 초기화합니다.
• r을 리스트 길이 - 1로 초기화합니다.
• l <= r인 동안 다음을 반복합니다:
  • mid := (l + r) // 2 (정수 나눗셈)
  • letters[mid] > target이면 r := mid - 1
  • 그렇지 않으면 l := mid + 1
• 반복이 끝나면 letters[l % len(letters)]를 반환합니다. 모듈로 연산을 사용하는 이유는 타겟이 리스트의 모든 문자보다 클 경우 순환하여 첫 번째 문자를 반환하기 위해서입니다.

구현 코드

class Solution:
    def nextGreatestLetter(self, letters, target):
        l = 0
        r = len(letters) - 1
        while l <= r:
            mid = (l + r)//2
            if letters[mid] > target:
                r = mid -1
            else:
                l = mid + 1
        return letters[l % len(letters)]
ob = Solution()
print(ob.nextGreatestLetter(["c", "f", "j"], "a"))

입력

["c", "f", "j"], "a"

출력

c

복잡도 분석

시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다.

공간 복잡도: O(1) — 추가적인 메모리를 거의 사용하지 않습니다.