소문자로만 이루어진 문자열 s가 주어졌다고 가정해 봅시다. 이 문제의 목표는 모든 알파벳이 최대 한 개의 조각에만 등장하도록 문자열을 최대한 많은 조각으로 분할한 뒤, 각 파티션(partition)의 크기를 리스트 형태로 반환하는 것입니다.
예를 들어 입력이 s = "momoplaykae"라면, 문자열은 ["momo", "p", "l", "ayka", "e"]처럼 다섯 개의 조각으로 나뉩니다. 모든 문자가 자신이 속한 조각 안에서만 등장하므로 조건을 만족하며, 따라서 출력은 [4, 1, 1, 4, 1]이 됩니다.
문제 해결 접근 방식
이 문제의 핵심은 어느 위치에서 문자열을 잘라도 되는지 판단하는 것입니다. 앞부분에서 등장한 모든 문자가 이후에 더 이상 나오지 않는 시점이 곧 파티션의 경계입니다. 이를 확인하기 위해 각 문자의 남은 등장 횟수를 카운터로 추적하고, 스택(stack)을 활용해 아직 완전히 처리되지 않은 문자들을 관리합니다.
구체적인 알고리즘은 다음과 같습니다.
- count := 문자열 s의 각 문자별 등장 횟수를 저장한 맵(Counter)
- out := 결과를 담을 새로운 리스트, stk := 빈 스택
- length := 현재 조각의 길이(초기값 0)
- 문자열 s의 각 문자 char에 대해 다음을 수행합니다.
- count[char]를 1 감소시키고, length를 1 증가시킵니다.
- count[char]가 0이 아니거나 stk가 비어 있지 않은 동안 아래를 반복합니다.
- count[char]가 0이 아니라면 → char를 stk에 push한 뒤 반복문을 종료합니다.
- stk가 비어 있지 않고 stk 맨 위 문자의 남은 횟수가 0이라면 → stk에서 pop합니다.
- 그렇지 않다면 → 반복문을 종료합니다.
- stk가 비어 있고 count[char]가 0이라면 → 지금까지의 length를 out에 추가하고 length를 0으로 초기화합니다.
- out을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
class Solution:
def solve(self, s):
count = Counter(s)
out = []
stk = []
length = 0
for char in s:
count[char] -= 1
length += 1
while count[char] != 0 or stk:
if count[char] != 0:
stk.append(char)
break
if stk and count[stk[-1]] == 0:
stk.pop()
else:
break
if not stk and count[char] == 0:
out += [length]
length = 0
return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))
입력
"momoplaykae"
출력
[4, 1, 1, 4, 1]
동작 원리 살펴보기
"momoplaykae" 예제를 기준으로 알고리즘의 흐름을 정리하면 다음과 같습니다.
- 'm'을 만나면 아직 뒤에서 'm'이 더 등장해야 하므로 스택에 잠시 쌓아 둡니다.
- "momo"까지 읽으면 'm'과 'o'의 남은 횟수가 모두 0이 되고 스택도 비워지는데, 이 시점에 첫 번째 파티션 "momo"(길이 4)가 확정됩니다.
- 'p'와 'l'은 한 번만 등장하므로 즉시 길이 1짜리 파티션이 각각 만들어집니다.
- "ayka" 구간 역시 같은 방식으로 처리되며, 'a'의 마지막 등장 시점에 스택이 비워지면서 길이 4의 파티션이 완성됩니다.
- 마지막 문자 'e'는 한 번만 등장하므로 길이 1의 파티션으로 마무리됩니다.
복잡도 분석
모든 문자는 최대 한 번씩 스택에 push되고 pop되므로 전체 시간 복잡도는 O(n)입니다. 공간 복잡도는 카운터와 스택에 저장되는 서로 다른 문자 수에 비례하며, 소문자 알파벳만 사용하는 경우 최대 26개이므로 사실상 상수 공간으로 볼 수 있습니다.