[1스4코2파] #154. LeetCode pattern 744. Find Smallest Letter Greater Than Target

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (154일차)
[4코1파] 2023.01.13~ (146일차)
[1스4코1파] 2023.04.12~ (57일차)
[1스4코2파] 2023.05.03 ~ (36일차)

Today :

2023.06.06 [154일차]
LeetCode Patterns
744. Find Smallest Letter Greater Than Target

744. Find Smallest Letter Greater Than Target

문제 설명

lowercase.. 영어 소문자 문자열로 구성된 letters 배열이 있고, target인 영어 소문자 문자열이 제공되는데, 해당 target 문자열보다는 사전적(lexicographically)으로 앞에 있으면서, 배열중에서는 가장 smallest 가장 빠른 순서인 문자열을 return 한다.
만약, target 보다 높은 문자열이 없다면은! letters  배열의 가장 첫번째 인덱스에 위치한 문자열을 return 한다!

문제 풀이 방법

이것 또한 binary search 로 푸는데,
여기서 약간 다른 건 target 문자열과 비교해서, 높은 문자열이 없으면 letters의 배열의 첫 번째 인덱스에 위치한 문자열을 retrun 해줘야 하는 조건과, 자기와 같은 문자열을 찾더라도 자기 문자열보다 높은 문자열을 retrun 해줘야 한다는 것이다 !

내 코드

class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        start, end = 0, len(letters)-1

        if target>= letters[-1] or target < letters[0]:
            return letters[0]

        while start <= end:
            mid = (start+end)//2
            if letters[mid]<=target:
                start = mid+1
            else:
                end = mid-1
        return letters[start]

증빙

여담

다른 새럼은 그냥 이진분류 구현 안하고, 배열 이진 분할 알고리즘 bisect을 활용해서 풀었더라고 세상 편하게 산다 나도 그럴란다