[Leetcode] 763. Partition Labels

문제내용

주어진 문자열 s를 파티션으로 나누면 되는 문제입니다. 여기서 파티션을 구분짓는 기준은 파티션 내 문자들이 각 파티션에서 최대 한번만 노출되어야합니다.

풀이

각 문자별로 for문을 이용하여 파티션 끝 값을 파악한 후에 해당 파티션 내 문자의 파티션이 가지고있는 파티션 범위가 포함되는지 확인한 후 길이를 반환하는 식으로 풀이했습니다.

class Solution:
    def partitionLabels(self, s: str) -> list[int]:
        list = [0] * 26

        #1.각각의 글자가 마지막으로 출현한 index를 파악한다.
        for i,char in enumerate(s):
            list[ord(char) - ord('a')] = i

        #2.파티션의 시작과 끝, 정답 list를 초기화한다
        partition_end = 0
        partition_start = 0
        partition_size = []

        for i,char in enumerate(s):
            #3.max를 이용하여 현재 글자의 파티션 끝과 이전 글자의 파티션 끝 값을 비교한다.
            partition_end = max(list[ord(char) - ord('a')],partition_end)

            #4.만일 현재 바라보고있는 문자의 파티션 끝이 현재 index 값이라면 하나의 파티션이 완성 된 것이다. size를 append해주고 start 값을 조정한다.
            if i == partition_end:
                partition_size.append(i-partition_start+1)
                partition_start = partition_end + 1
        return partition_size