[LeetCode] 763. Partition Labels

출처

763. Partition Labels

---

문제

주어진 문자열 s를 분할하는데, 각각의 문자가 한 파티션에 최대한 많이 들어가도록 최대한 많이 분할한 뒤, 각각의 분할된 문자열의 길이를 list 형태로 return하는 문제이다.
주어진 예제인 "ababcbacadefegdehijhklij"를 위의 조건으로 분할하면, "ababcbaca", "defegde", "hijhklij"와 같이 세 부분으로 분할된다. 부분의 최적해를 구해 최종 결과를 도출하는 그리디 알고리즘으로 풀어보았다.

---

풀이

이 문제의 핵심은 각 문자의 마지막 위치를 기준으로 문자열을 분할하는 것이다. 26개의 알파벳 문자의 마지막 위치를 저장할 배열을 선언하고, 반복문을 통해 문자열 내부에서의 각 문자의 마지막 위치 (인덱스)를 저장한다.

position = [0 for _ in range(26)]

for i in range(len(s)):
	position[ord(s[i]) - ord('a')] = i

예를 들어, "accabbd"라는 문자열이 입력값으로 들어왔다고 가정하면 다음과 같이 위치 정보가 저장될 것이다.

문자	마지막 위치
a	3
b	5
c	2
d	6

이제 어떤 문자열을 기준으로 파티션을 분할해야 하는지 생각해보도록 하자.

• 문자열을 하나씩 탐색하면서 해당 문자열의 마지막 위치를 조회한다.
• 탐색한 문자열의 마지막 위치가 이전 문자열의 마지막 위치보다 뒤에 있으면 갱신한다.
• 탐색한 문자열의 마지막 위치와 현재의 위치가 일치하면 해당 문자까지 한 파티션으로 분할한다.

해당 알고리즘을 코드로 구현하면 다음과 같다.

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        answer = []
        position = [0 for _ in range(26)]
    
        for i in range(len(s)):
            position[ord(s[i]) - ord('a')] = i
            
        start, end = 0, 0
        for i in range(len(s)):
            end = max(position[ord(s[i]) - ord('a')], end)
            if i == end:
                answer.append(end - start + 1)
                start = i + 1
                
        return answer

---

시간복잡도

$O(N)$

---

실행 결과