문제 개요
문자열 s가 주어졌을 때, 가장 앞에 나타나는 연속된 중복 문자 묶음을 반복적으로 삭제한 후 최종적으로 남는 문자열을 구하는 문제입니다.
예를 들어 입력이 s = "xyyyxxz"라면 결과는 "z"입니다. 먼저 첫 번째 연속 중복인 "yyy"를 삭제하면 "xxxz"가 되고, 이어서 "xxx"를 삭제하면 최종적으로 "z"만 남게 됩니다.
접근 방법: 스택(Stack) 활용
이 문제는 스택 자료구조를 활용하면 한 번의 순회로 효율적으로 해결할 수 있습니다. 알고리즘의 핵심 흐름은 다음과 같습니다.
- 빈 스택을 준비하고 인덱스 변수 i를 0으로 초기화합니다.
- i가 문자열 길이보다 작은 동안 다음을 반복합니다.
- 스택이 비어 있지 않고 스택의 맨 위(top) 값이 s[i]와 같다면, 스택에서 값을 꺼낸 뒤(x) 같은 문자가 계속되는 동안 i를 전진시키고, 마지막에 i를 하나 되돌립니다.
- 그렇지 않으면 현재 문자 s[i]를 스택에 push합니다.
- 매 반복이 끝날 때마다 i를 1씩 증가시킵니다.
- 모든 문자를 처리한 후 스택의 요소들을 이어 붙여 반환합니다.
Python 구현 코드
class Solution:
def solve(self, s):
stack = []
i = 0
while i < len(s):
if len(stack) and stack[-1] == s[i]:
x = stack.pop()
while i < len(s) and x == s[i]:
i += 1
i -= 1
else:
stack.append(s[i])
i += 1
return "".join(stack)
ob = Solution()
s = "xyyyxxz"
print(ob.solve(s))
실행 결과
입력:
"xyyyxxz"
출력:
z
동작 과정 단계별 추적
- i = 0: 스택이 비어 있으므로 'x'를 push → 스택: ['x']
- i = 1: 스택 top 'x'와 'y'가 다르므로 'y'를 push → 스택: ['x', 'y']
- i = 2: 스택 top 'y'와 'y'가 같으므로 pop한 뒤 'yyy' 전체를 건너뜀 → 스택: ['x'], i는 'x' 위치(4)로 이동
- i = 4: 스택 top 'x'와 'x'가 같으므로 pop한 뒤 'xxx' 전체를 건너뜀 → 스택: [], i는 'z' 위치(6)로 이동
- i = 6: 스택이 비어 있으므로 'z'를 push → 스택: ['z']
- 반복이 종료되면 스택 요소를 연결해 최종 결과 "z"를 반환합니다.
시간 및 공간 복잡도
각 문자는 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 스택에 저장되는 문자 수에 비례하므로 역시 O(n)입니다.