문제9 - 짝지어 제거하기 (Python)

프로그래머스

문자열 내에서 인접한 동일 알파벳 쌍을 찾아 연속적으로 제거하고, 최종적으로 모든 문자가 제거될 수 있는지 판별하는 문제입니다. 문자열의 최대 길이가 1,000,000에 달하므로 효율적인 탐색 알고리즘이 필수적입니다.

---

1.  나의 풀이 (Modular Approach)

스택(Stack) 구조를 활용하여 선형 시간 내에 문제를 해결했습니다. 파이썬의 collections.deque를 사용하여 스택의 동작을 구현했습니다.

from collections import deque

def solution(s):
    # 자료구조로 스택을 사용하기 위해 deque를 선언합니다.
    stack = deque()

    for char in s:
        # 1. 스택이 비어있지 않고, 마지막 요소가 현재 문자와 같으면 제거합니다.
        if stack and stack[-1] == char:
            stack.pop()
        # 2. 그렇지 않으면 현재 문자를 스택에 추가합니다.
        else:
            stack.append(char)
            
    # 스택이 비어있으면(모두 제거됨) 1, 남아있으면 0을 반환합니다.
    return 0 if stack else 1

---

2.  오늘 배운 점 및 복기 노트

스택 자료구조의 직관적 활용

인접한 요소를 비교하여 제거하는 문제는 스택의 '후입선출(LIFO)' 특성이 가장 잘 들어맞는 유형임을 복기했습니다. 새로운 요소를 추가하기 전에 바로 직전의 요소(Stack Top)를 확인하는 것만으로도 $O(n)$ 시간에 전체 문자열을 처리할 수 있습니다.

컬렉션의 불리언(Boolean) 판정

파이썬에서는 if len(stack) > 0: 대신 if stack:과 같이 작성하는 것만으로도 비어있는지 여부를 판정할 수 있습니다. 이는 파이썬다운(Pythonic) 코드 작성법이며 가독성을 높여줍니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

시간 복잡도의 한계 인지

문제의 제한사항에서 문자열 길이가 1,000,000인 경우, $O(n^2)$ 알고리즘은 반드시 시간 초과가 발생함을 명시하고 있습니다. 문자열을 슬라이싱하여 다시 합치는 방식(s[:i] + s[i+2:])은 매번 새로운 문자열 객체를 생성하므로 $O(n)$의 비용이 들고, 이를 반복하면 전체 복잡도가 $O(n^2)$이 되어 효율성 테스트를 통과할 수 없습니다.

입력값의 크기와 알고리즘 선택의 상관관계

교재에서는 입력값이 백만 개일 때 $O(n)$ 혹은 $O(n \log n)$으로 풀어야 한다는 가이드라인을 제시합니다. 이는 코딩 테스트 도중 알고리즘의 방향성을 결정하는 데 매우 중요한 기준이 됩니다. 단순 계산으로도 1억 번 이상의 연산이 예상된다면 즉시 접근법을 수정해야 합니다.

발상의 전환: 실시간 처리

전체 문자열에서 쌍을 찾아 제거하고 다시 처음부터 탐색하는 것이 아니라, 문자를 하나씩 읽으며 '실시간'으로 스택에 쌓고 쌍이 맞으면 즉시 터뜨리는 방식의 효율성을 강조합니다. 이는 문제 설명에 나온 '제거 후 앞뒤로 이어 붙인다'는 표현을 물리적인 문자열 연산으로 보지 않고 논리적인 스택 연산으로 치환한 결과입니다.