이 문제는 LeetCode 20번, 유효한 괄호에 관한 것입니다.

주어진 문자열은 다음 여섯 가지 문자만 포함합니다:

• (
• )
• [
• ]
• {
• }

이 문자열이 "유효한지" 판단해야 합니다.

유효하다는 것은 다음을 의미합니다:

1. 왼쪽 괄호는 같은 타입의 오른쪽 괄호로 닫혀야 합니다.
2. 왼쪽 괄호는 올바른 순서로 닫혀야 합니다.
3. 모든 오른쪽 괄호에는 해당 왼쪽 괄호가 있어야 합니다.

예시 1

s = "()"

출력:

True

예시 2

s = "()[]{}"

출력:

True

예시 3

s = "(]"

출력:

False

이 문제는 처음에는 "괄호 짝 맞추기" 문제처럼 보이지만, 많은 초보자들이 흔히 잘못된 접근 방식에 빠지기 쉽습니다.

잘못된 접근 방식: 현재 왼쪽 괄호 바로 뒤에 해당 오른쪽 괄호가 오는지 확인하는 것입니다.

왜 "이웃한 두 문자만 확인하는 것"이 틀렸는가

처음 생각할 수 있는 코드는 다음과 같을 수 있습니다:

if char == "(" and next_char != ")":
    return False

이는 현재 문자가 (라면, 바로 다음 문자가 )여야 한다는 의미입니다.

하지만 이 문제는 단순히 "인접한 두 문자가 짝을 이루는지"를 판단하는 것이 아니라, 문자열 전체의 중첩 구조가 올바른지를 판단해야 합니다.

예를 들어, 다음 문자열을 생각해 봅시다:

s = "([])"

이 문자열은 유효합니다. 왜냐하면:

• 가장 바깥쪽의 (와 )가 짝을 이룹니다.
• 중간의 [와 ]가 짝을 이룹니다.

하지만 이웃한 문자만 확인한다면:

• 첫 번째 문자는 (입니다.
• 바로 뒤에 오는 문자는 [이며, )가 아닙니다.

이 경우 False로 잘못 판단하게 됩니다.

따라서 이 문제의 핵심은 다음과 같습니다:

일부 괄호는 짝을 이루지만, 반드시 서로 붙어 있지는 않을 수 있습니다.

즉, s[i]와 s[i+1]만으로는 판단할 수 없습니다.

이 문제가 실제로 묻는 것은 무엇인가

이 문제는 다음을 묻고자 합니다:

오른쪽 괄호를 만날 때마다, 그것은 "가장 최근에 나왔지만 아직 짝이 맞지 않은 왼쪽 괄호"와 짝을 이루어야 합니다.

이 문장의 핵심 단어는 다음과 같습니다:

가장 최근에 나온, 아직 짝이 맞지 않은 왼쪽 괄호

이것은 전형적인 "후입선출 (Last-In, First-Out, LIFO)" 문제입니다. 즉, 나중에 들어온 왼쪽 괄호가 먼저 짝을 이루어 제거되어야 합니다.

이것이 바로 스택 (stack)의 특징입니다.

스택: 어렵지 않게 생각해보자

"스택"이라는 단어가 자료구조 수업의 개념처럼 들릴 수 있지만, 간단하게 생각하면 다음과 같습니다:

• 접시를 쌓는 것과 같습니다.
• 새로 올린 접시는 가장 위에 있습니다.
• 접시를 가져갈 때는 가장 위에 있는 접시만 가져갈 수 있습니다.

따라서 특징은 다음과 같습니다:

나중에 넣은 것이 먼저 나옵니다. (LIFO)

Python에서는 리스트를 사용하여 스택을 쉽게 구현할 수 있습니다:

stack = []

요소 추가 (Push)

stack.append('(')

요소 제거 (Pop)

stack.pop()

예를 들어:

stack = []
stack.append('(')
stack.append('[')
print(stack)
# 출력: ['(', '[']

stack.pop() # '['가 먼저 제거됩니다.

스택은 괄호 문제를 처리하는 데 매우 적합합니다.

이 문제의 핵심 로직

문자열을 왼쪽에서 오른쪽으로 순회합니다.

왼쪽 괄호를 만났을 때

해당 왼쪽 괄호를 스택에 넣습니다.

• (를 만나면 스택에 추가합니다.
• [를 만나면 스택에 추가합니다.
• {를 만나면 스택에 추가합니다.

오른쪽 괄호를 만났을 때

스택의 가장 위(top)에 있는 왼쪽 괄호와 현재 오른쪽 괄호가 짝을 이루는지 확인합니다.

• )를 만나면, 스택의 top은 (여야 합니다.
• ]를 만나면, 스택의 top은 [여야 합니다.
• }를 만나면, 스택의 top은 {여야 합니다.

짝이 맞지 않으면 즉시 False를 반환합니다.

문자열 순회가 끝났을 때 스택이 비어 있다면, 모든 괄호가 성공적으로 짝을 이룬 것이므로 True를 반환합니다.

초보자를 위한 가장 이해하기 쉬운 코드

다음은 이해하기 쉬운 코드입니다:

def is_valid(s):
    """
    :type s: str
    :rtype: bool
    """
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}

    for char in s:
        if char in mapping: # 오른쪽 괄호인 경우
            # 스택이 비어있거나, 스택에서 팝한 값이 매핑된 왼쪽 괄호와 다르면 False
            if not stack or stack.pop() != mapping[char]:
                return False
        else: # 왼쪽 괄호인 경우
            stack.append(char)

    # 문자열 순회 후 스택이 비어있으면 True, 아니면 False
    return not stack

코드 각 줄 설명

1. 스택 초기화

stack = []

stack은 왼쪽 괄호를 저장하는 데 사용됩니다. "매칭 대기 괄호 창고"로 생각할 수 있습니다.

2. 괄호 짝 매핑

mapping = {")": "(", "]": "[", "}": "{"}

오른쪽 괄호를 키로, 해당하는 왼쪽 괄호를 값으로 하는 딕셔너리를 사용하여 짝을 쉽게 확인할 수 있습니다.

3. 문자열 순회

for char in s:

문자열의 각 문자를 순서대로 처리합니다.

4. 오른쪽 괄호 처리

if char in mapping: # 오른쪽 괄호인 경우
    # 스택이 비어있거나, 스택에서 팝한 값이 매핑된 왼쪽 괄호와 다르면 False
    if not stack or stack.pop() != mapping[char]:
        return False

현재 문자가 오른쪽 괄호이면 (즉, mapping 딕셔너리의 키 중에 있다면):

• 스택이 비어있는지 확인합니다. 비어 있다면, 짝을 이룰 왼쪽 괄호가 없으므로 False를 반환합니다.
• 스택이 비어있지 않다면, 스택에서 가장 최근에 추가된 왼쪽 괄호(stack.pop())를 가져와 mapping을 통해 해당 오른쪽 괄호와 짝이 맞는지 비교합니다. 짝이 맞지 않으면 False를 반환합니다.

5. 왼쪽 괄호 처리

else: # 왼쪽 괄호인 경우
    stack.append(char)

현재 문자가 왼쪽 괄호이면 (즉, mapping 딕셔너리의 키에 없다면), 스택에 추가합니다. 나중에 나올 오른쪽 괄호와 짝을 맞추기 위해 대기시킵니다.

6. 최종 스택 상태 확인

return not stack

문자열 전체를 순회한 후, 스택이 비어 있으면 모든 괄호가 올바르게 짝을 이룬 것이므로 True를 반환합니다. 스택에 왼쪽 괄호가 남아 있다면, 짝이 맞지 않은 것이므로 False를 반환합니다.

수동으로 시뮬레이션해보기

예시: s = "({[]})"

1. stack = []
2. char = '(': 왼쪽 괄호이므로 스택에 추가. stack = ['(']
3. char = '{': 왼쪽 괄호이므로 스택에 추가. stack = ['(', '{']
4. char = '[': 왼쪽 괄호이므로 스택에 추가. stack = ['(', '{', '[']
5. char = ']': 오른쪽 괄호. mapping[']']는 '['. 스택에서 stack.pop()하면 '['. '[' == '['이므로 짝이 맞습니다. stack = ['(', '{']
6. char = '}': 오른쪽 괄호. mapping['}']는 '{'. 스택에서 stack.pop()하면 '{'. '{' == '{'이므로 짝이 맞습니다. stack = ['(']
7. char = ')': 오른쪽 괄호. mapping[')']는 '('. 스택에서 stack.pop()하면 '('. '(' == '('이므로 짝이 맞습니다. stack = []

문자열 순회 완료. 스택이 비어 있으므로 True 반환.

이 문제의 본질

이 문제는 괄호 매칭처럼 보이지만, 실제로는 두 가지 능력을 시험합니다.

1. "후입선출" 상황 인식

다음과 같은 상황이라면 스택을 떠올려야 합니다:

• 나중에 들어온 것이 먼저 처리되어야 할 때
• 가장 최근 항목이 우선적으로 처리되어야 할 때

2. 추상적인 규칙을 프로세스 제어로 변환

문제 설명:

• 왼쪽 괄호는 해당하는 오른쪽 괄호와 짝을 이루어야 합니다.
• 순서도 정확해야 합니다.

이를 프로그램 로직으로 변환해야 합니다:

• 왼쪽 괄호는 스택에 넣습니다.
• 오른쪽 괄호는 스택의 최상단과 비교합니다.
• 최종적으로 스택은 비어 있어야 합니다.

이 단계는 문제 해결 과정에서 매우 중요합니다.

처음 문제 풀이를 시작하는 당신에게

만약 이 문제를 처음 접했을 때 "이웃한 문자가 짝을 이루는지 확인해야겠다"고 생각했다면, 그것은 전혀 이상한 것이 아닙니다. 사람은 누구나 처음에는 가장 직관적인 방법으로 문제를 해결하려고 합니다.

중요한 것은 처음부터 정답을 맞추는 것이 아니라, 다음과 같은 점을 점진적으로 깨닫는 것입니다:

• 언제 이웃한 문자만 보는 것으로는 부족한가?
• 언제 이전 정보를 기억해야 하는가?
• 언제 스택을 생각해야 하는가?

이것이 바로 문제 풀이의 가치입니다.

만약 "오른쪽 괄호는 뒤의 문자를 찾는 것이 아니라, 앞에 있는 가장 최근의 짝짓기 안 된 왼쪽 괄호를 찾아야 한다"는 점을 이해했다면, 이 문제의 절반 이상을 이해한 것입니다.

요약

이 문제의 핵심은 단 한 문장입니다:

오른쪽 괄호를 만날 때마다, 그것은 가장 최근에 나온 짝짓기 안 된 왼쪽 괄호와 짝을 이루어야 합니다.

따라서 이 문제는 스택을 사용하는 것이 가장 적합합니다.

초보자가 가장 이해하기 쉬운 기본 코드는 다음과 같습니다:

def is_valid(s):
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}

    for char in s:
        if char in mapping:
            if not stack or stack.pop() != mapping[char]:
                return False
        else:
            stack.append(char)

    return not stack

이 문제를 제대로 이해하면, 이후의 "괄호 매칭", "식 처리", "스택 구조" 관련 문제들을 훨씬 수월하게 풀 수 있습니다.

마무리: Easy 문제라도 가볍게 보지 말자

유효한 괄호는 Easy 난이도의 문제이지만, "스택 입문 첫 번째 문제"로 매우 적합합니다. 이 문제는 당신을 "눈앞의 두 문자만 보는 것"에서 "동적인 매칭 구조를 관리하는 것"으로 나아가게 합니다.

이 단계는 많은 알고리즘 문제에서 가장 중요한 성장 과정입니다:

국소적인 부분만 보지 않고, 전체 과정에서의 상태를 관리하기 시작합니다.

따라서 이 문제를 이해했다면, 단순히 "답을 외우는 것" 이상으로 다음을 기억하는 것이 더 가치 있습니다:

• 왜 이웃한 문자만 판단하는 것이 안 되는가?
• 왜 스택을 생각해야 하는가?
• 왜 마지막에 스택이 비어 있는지 확인해야 하는가?

이 세 가지 질문에 대한 답을 명확히 이해하면, 이 문제는 단순히 "푼 문제"가 아니라 "완전히 내 것으로 만든 문제"가 될 것입니다.