leetcode.com 763. Partition Labels

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

파이썬 소스: https://bit.ly/48LfUEP

스트링 s에서 첫 글자를 때서, 2개의 리스트로 나눠 보겠습니다.

s[:1] , s[1:]으로 나누고, 2개의 리스트를 set()으로 변환한 뒤에, intersection() 메서드로 공통된 원소가 있는지에 확인해 봅니다. s[:1]의 길이가 1이기 때문에, intersection()의 리턴값인 set의 길이는 1또는 0 입니다. 코드로 구현하면 아래와 같습니다.

set_part = set(s[:1]) set_right = set(s[1:]) intersection = set_part.intersection(set_right)

 

-      Intersection의 길이가 0 이라는 의미는 s[1:] 과 s[:1]사이에 같은 원소가 없다는 뜻 입니다. 따라서, 1이 partition할 위치가 됩니다.

-      반대로 1이라는 의미는 s[:1]과 같은 글자가 s[1:]안에 포함되어 있다는 의미입니다. 문제에 따라서, parts as possible so that each letter appears in at most one part. 이 문장대로, 하나의 파트에 최대한 같은 글자가 많이 들어 있도록 partition을 해야 합니다. 그러므로, s[1:]과 같은 글자가 s[1:]에 들어 있기 때문에, 인덱스 2를 확인해 봐야 합니다.

 

s의 길이로 루프를 만들고, 파티션에 포함될 부분을 set_part = set()로, 파티션에 포함되지 않을 부분을 set_right = set(s[i:])로 아래와 같이 구현합니다. 두 set 사이에 intersection이 0이면 파티션을 나눠야 하구요, 0 보다 크다면, 파티션의 크기를 더 크게 할 수 있습니다.

 

from typing import List class Solution:     def partitionLabels(self, s: str) -> List[int]:         set_part = set()         partition_length = 0         answer = []         for i in range(len(s)):             if len(set_part) > 0:                 set_right = set(s[i:])                 intersection = set_part.intersection(set_right)                 if len(intersection) == 0:                     set_part.clear()                     answer.append(partition_length)                     partition_length = 0             set_part.add(s[i])             partition_length += 1         if partition_length != 0:             answer.append(partition_length)         return answer

 

코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul