문자열 text가 주어졌을 때, text에 등장하는 모든 고유한 문자를 각각 정확히 한 번씩 포함하면서 사전순으로 가장 작은 부분 시퀀스(subsequence)를 찾는 것이 목표입니다. 예를 들어 입력이 "cdadabcc"라면 출력은 "adbc"가 됩니다.
접근 방법: 그리디 + 단조 스택
이 문제는 단조 스택(monotonic stack)과 그리디(greedy) 기법을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 문자가 마지막으로 등장하는 인덱스를 미리 기록해 둡니다.
- 새 문자를 처리할 때 스택 맨 위 문자보다 현재 문자가 더 작고, 맨 위 문자가 뒤에서 다시 등장할 수 있다면 맨 위 문자를 제거(pop)합니다. 이렇게 하면 더 작은 문자를 앞쪽에 배치해 결과를 사전순으로 줄일 수 있습니다.
- 이미 스택에 포함된 문자는 다시 넣지 않아, 모든 고유 문자가 정확히 한 번씩만 등장하도록 보장합니다.
알고리즘 단계
- 스택 st와 두 개의 맵 last_o(문자별 마지막 등장 인덱스), considered(문자별 스택 포함 여부)를 빈 상태로 초기화합니다.
- i를 len(text)-1부터 0까지 역순으로 순회하며, text[i]가 last_o에 없다면 last_o[text[i]] := i, considered[text[i]] := false로 설정합니다.
- i := 0으로 두고, i가 len(text)보다 작은 동안 아래를 반복합니다.
- 스택이 비어 있으면: text[i]를 push하고 considered[text[i]] := true로 만든 뒤 i를 1 증가시킵니다.
- 스택 top > text[i]이고 considered[text[i]] == false인 경우:
- last_o[스택 top] > i이면(맨 위 문자가 뒤에 다시 등장하면) considered[스택 top] := false로 바꾸고 pop합니다.
- 그렇지 않으면 considered[text[i]] := true로 설정하고 text[i]를 push한 뒤 i를 1 증가시킵니다.
- 스택 top < text[i]이고 considered[text[i]] == false인 경우: text[i]를 push하고 considered[text[i]] := true로 만든 뒤 i를 1 증가시킵니다.
- 그 외의 경우에는 단순히 i를 1 증가시킵니다.
- 반복이 끝나면 스택에 남아 있는 문자들을 순서대로 이어 붙여 반환합니다.
구현 예제
class Solution(object):
def smallestSubsequence(self, text):
"""
:type text: str
:rtype: str
"""
stack = []
last_o = {}
considered = {}
for i in range(len(text)-1, -1, -1):
if text[i] not in last_o:
last_o[text[i]] = i
considered[text[i]] = False
i = 0
while i < len(text):
if len(stack) == 0:
stack.append(text[i])
considered[text[i]] = True
i += 1
elif stack[-1] > text[i] and considered[text[i]] == False:
if last_o[stack[-1]] > i:
considered[stack[-1]] = False
stack.pop()
else:
considered[text[i]] = True
stack.append(text[i])
i += 1
elif stack[-1] < text[i] and considered[text[i]] == False:
stack.append(text[i])
considered[text[i]] = True
i += 1
else:
i += 1
return "".join(i for i in stack)
입력
"cdadabcc"
출력
"adbc"
복잡도 분석
시간 복잡도는 O(n)이며, 공간 복잡도는 O(k)(k는 고유 문자의 개수)입니다. 각 문자는 최대 한 번 push되고 한 번 pop되므로 전체 과정이 선형 시간 안에 완료됩니다.