LeetCode 763. Partition Labels

문제 링크 : https://leetcode.com/problems/partition-labels/

주어진 배열이 partition (ex. 1234156 을 예로 들자면
1234156을 나누었을때 겹치는 글자가 없이 나누어야한다(라고 대충 이해를 함)
-> 12341, 56
) 이 되도록 나누는 문제이다.

쉬울줄 알았는데 생각보다 어려웠다.
결국 유튜브로 구글링해서 안 해결책을 보자면

ababcbacadefegdehijhklij
을 예로 들었을 때,
처음 a부터 시작하여 겹치는 문자가 있을 경우 그 문자의 idx를 그룹으로 나누는 인덱스(end)로 잡는다.
그리고 이후에 end에 해당하는 문자까지 겹치는 인덱스가 있다면.. 그 값을 업데이트해준다..

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        dic={}
        
        for i, c in enumerate(s):
            dic[c] = i
            
        ans = []
        start , end = 0, 0
        
        for i,c in enumerate(s):
            start += 1
            end = max(end,dic[c])
            
            if end == i:
                ans.append(start)
                start = 0
                
            
        return ans
        

Runtime: 45 ms, faster than 77.01% of Python3 online submissions for Partition Labels.
Memory Usage: 13.9 MB, less than 72.84% of Python3 online submissions for Partition Labels

07.06.22
다시 풀어봐도 매우.. 어렵다,,,,,,

enumerate의 경우 중복된 숫자들의 경우 가장 마지막 인덱스..?를 반환해주나보다..?(대충 이렇게 이해함

그렇게해서 각 숫자별로 마지막 인덱스를 파악하여서 파티션을 나누는... 알고리즘.. 이다