[1스4코2파] #262. Leetcode 763. Partition Labels

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

START :

[3코1파] 2023.01.04~ (262일차)
[4코1파] 2023.01.13~ (254일차)
[1스4코1파] 2023.04.12~ (166일차)
[1스4코2파] 2023.05.03 ~ (144일차)

Today :

2023.09.22 [262일차]

Leetcode 763. Partition Labels

https://leetcode.com/problems/partition-labels/

문제 설명

주어진 문자열 s를 최대한 많은 부분 문자열로 분할해서 해당 분할된 문자열의 수를 리스트에 담아서 리턴하는 문제이다. 여기서는 각 부분 문자열이 분할된 다른 문자열과 중복된 문자열이 없어야하고,
위 조건을 만족하면서 최대한 많은 부분 문자열로 쪼개는 문제이다.

문제 풀이 방법

hash table을 이용해서 주어진 문자열에서 구성된 개별 문자의 가장 마지막 인덱스를 담는다.
그리고 주어진 문자열을 enumerate를 이용해서 인덱스와 각 개별 문자열을 얻고,
size와 last index 즉, 개발 문자열의 마지막 인덱스와 비교하면서 size가 last index보다 넘어가면
순회하면서 +1씩 더했던 size를 리스트에 담고, 다시 0으로 할당한다.
이렇게 전체 문자열을 순회한다
시간복잡도는 O(n)
공간복잡도는 O(26)으로 O(1)로 해결할 수 있는 그리디 알고리즘이다.

내 코드

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        lastIndex = {}

        for i, c in enumerate(s):
            lastIndex[c] = i
    
        ans = []
        size, end = 0, 0
        for i, c in enumerate(s):
            size += 1
            if lastIndex[c] > end:
                end = lastIndex[c]
            end = max(end, lastIndex[c])

            if i == end:
                ans.append(size)
                size = 0
        
        return ans

증빙

여담

이탈리아 여행 끝나고 릿코드로 돌아왔습니다 빠밤