Python으로 문자열의 인접 중복 문자 모두 제거하기

문제 개요

소문자로만 이루어진 문자열 S가 주어졌을 때, 중복 제거(duplicate removal) 연산을 수행하는 문제입니다. 중복 제거란 서로 인접해 있고 같은 두 글자를 선택하여 삭제하는 것을 의미합니다.

이 연산을 반복적으로 수행하여 더 이상 제거할 수 있는 인접 중복이 남아 있지 않을 때까지 진행한 뒤, 최종 결과 문자열을 반환하면 됩니다. 답은 항상 유일하다는 것이 보장되어 있습니다.

예시

문자열이 "abbacaca"라고 가정해 보겠습니다. 정답은 "caca"입니다.

• 먼저 인접한 중복 "bb"를 제거하면 → "aacaca"
• 다음으로 인접한 중복 "aa"를 제거하면 → "caca"
• 더 이상 인접한 중복이 없으므로 최종 결과는 "caca"

풀이 접근 방법: 스택 활용

이 문제는 스택(Stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.

• 스택 역할을 할 배열 st를 선언하고, 인덱스 i를 0으로 초기화합니다.
• i가 문자열의 길이보다 작은 동안 반복합니다.
  • st에 요소가 존재하고, st의 마지막 요소가 현재 문자 S[i]와 같다면 i를 1 증가시키고 st의 마지막 요소를 제거(팝)합니다.
  • 그렇지 않다면 S[i]를 st에 추가(푸시)하고 i를 1 증가시킵니다.
• 반복이 끝나면 st의 모든 요소를 하나의 문자열로 합쳐서 반환합니다.

핵심 아이디어는 새로 들어오는 문자가 스택의 최상단(top) 문자와 같으면 두 문자가 서로 제거된다는 점입니다. 이렇게 하면 한 번의 순회로 모든 인접 중복을 처리할 수 있습니다.

Python 구현 코드

class Solution(object):
    def removeDuplicates(self, S):
        st = []
        i = 0
        while i < len(S):
            if len(st) != 0 and st[-1] == S[i]:
                i += 1
                st.pop(-1)
            else:
                st.append(S[i])
                i += 1
        return "".join(i for i in st)

ob1 = Solution()
print(ob1.removeDuplicates("abbacaca"))

실행 결과

입력

"abbacaca"

출력

"caca"

복잡도 분석

• 시간 복잡도: O(n) — 문자열의 각 문자를 정확히 한 번씩만 처리합니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 문자가 스택에 저장될 수 있습니다.

이처럼 스택을 활용하면 직관적이면서도 선형 시간 안에 인접 중복 제거 문제를 깔끔하게 해결할 수 있습니다.