[LeetCode] 744. Find Smallest Letter Greater Than Target

문제

문제는 어렵지 않다. 오름차순으로 정렬되어 있는 letters안에 target보다 큰 문자를 return, 만약 없다면 첫번째 문자 return

시간복잡도 : O(n)

class Solution:  
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:  
        ans = letters[0]  
        for letter in letters:  
            if letter > target:  
                return letter  
        return ans

시간복잡도 O(logn)

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
            l, r = 0, len(letters)
            while l < r:
                c = (l + r) // 2
                if letters[c] > target:
                    r = c
                else:
                    l = c + 1
            if l == len(letters):
                return letters[0]
        return letters[l]

오히려 n보다 조금 더 느리게 나왔다. n의 개수가 적기 때문에 그런 것 같다.

여러 방식으로 풀어보는 재미를 느끼게 해준 문제였다.

읽어보면 좋은 글

끝