[Leetcode] 763. Partition Labels

문제 바로가기

제일 앞 문자부터 시작(start)

1. cur(현재 문자)의 가장 마지막 등장 위치를 cur_end(현재 최대 끝 위치)에 저장
2. cur_end가 end보다 클 경우 end 갱신
3. end 도달할 때까지 1~2번을 반복
4. 반복 끝나면 [start, end]를 한 part로 구분
5. start = end+1 갱신하고 1~4 단계 반복

Time Complexity: $O(n)$
Space Complexity: $O(1)$ - 알파벳 개수 26개를 넘지 않는다.

Runtime: 40 ms, faster than 70.06% of Python3 online submissions for Partition Labels.
Memory Usage: 14.2 MB, less than 55.79% of Python3 online submissions for Partition Labels.

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        ans = []
        last_entry = dict()
        leng = len(s)
        start = 0
        if start == leng:
            return [0]
        
        # 각 문자별 마지막 등장 위치를 기록
        for c in s:
            if c not in last_entry:
                last_entry[c] = s.rfind(c)
        
        while start < leng:
            end = last_entry[s[start]]
            cur = start + 1
            while cur < end < leng - 1:
                cur_end = last_entry[s[cur]]
                end = max(end, cur_end)
                cur += 1
            ans.append(end - start + 1)
            start = end + 1
        return ans

solution

위에서 작성했던 답변은 while문에 2번 쓰였는데, 결국 문자열 s를 탐색하게되므로 for문으로 작성하는 것이 더 직관적일 것이라는 생각이 들었다.

아래의 코드는 leetcode에서 제공하는 solution이다.
같은 흐름으로 해결하지만 훨씬 더 간결하고 보기 쉬운 코드로 작성되어 있다.

Runtime: 40 ms, faster than 70.06% of Python3 online submissions for Partition Labels.
Memory Usage: 14.1 MB, less than 92.93% of Python3 online submissions for Partition Labels.

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        ans = []
        last_entry = dict()
        # 각 문자별 마지막 등장 위치를 기록
        for idx, c in enumerate(s):
            last_entry[c] = idx
        
        start_idx = end_idx = 0
        for cur_idx, cur in enumerate(s):
            end_idx = max(end_idx, last_entry[cur])
            if cur_idx == end_idx:
                ans.append(end_idx - start_idx + 1)
                start_idx = cur_idx + 1
                
        return ans