문제 다시 분석

생각이 바뀌었으니 문제를 다시 분석해야 합니다.

1. 받은 문자열을 for 문으로 1글자씩 읽습니다.

2. 배열에 알파벳을 하나씩 넣고, 만약 배열의 마지막 알파벳과 현재 순회 중인 알파벳이 같다면 배열에서 해당 요소를 제거합니다.

3. 모든 문자열을 다 돌았을 때 배열에 값이 없다면 모두 짝지은 것이고, 남아 있다면 모두 짝짓지 못한 것입니다.

좋습니다. 이 정도면 충분히 구현할 수 있겠군요. 추가로 배열에서 없는 인덱스를 조회하면 프로그램에서 오류가 발생하기 때문에 항상 배열이 비어 있는지 확인합시다.

이번에도 결과 코드가 짧으므로 바로 정답을 확인해보겠습니다.

전체 코드

def solution(s):
    stack = []
    for case in s:
        if stack and stack[-1] == case: stack.pop() #스택에 값이 있고 마지막이 같은지
        else: stack.append(case)
    return 0 if stack else 1

코드가 매우 간결해졌습니다. 생각만 바꿨을 뿐인데 문제를 너무 쉽게 풀었네요. 스택을 사용하니 O(n) 시간 안에 문제를 풀 수 있었습니다. 만약 비슷한 문제가 나왔는데, 문제 설명이 함정이라는 것을 깨닫고 바로 스택을 사용했다면 푸는 데 10분도 안 걸리지만, 그렇지 않았다면 몇 시간 동안 붙잡고 있다가 정답을 보고 ‘이렇게 간단한 거야?’라면서 허무하다고 생각했을 겁니다.

아이디어를 떠올리지 못했다고 자책하지 마세요. 발상의 전환은 경험이 중요합니다. 책에 있는 문제를 풀면서 하나씩 배워나간다면 충분히 생각해낼 수 있을 겁니다.