20. 유효한 괄호

이 문제는 주어진 문자열이 유효한 괄호 문자열인지 판단하는 문제입니다. 문자열은 '(', ')', '{', '}', '[', ']'로만 구성되어 있으며, 올바른 괄호 문자열은 열리는 괄호가 닫히는 괄호와 짝을 이루어야 하고, 그 순서도 맞아야 합니다.

이 문제를 해결하기 위해 스택 자료구조를 사용합니다. 스택은 LIFO(Last In, First Out) 구조로, 가장 최근에 추가된 요소가 가장 먼저 제거되는 특징을 가지고 있습니다. 이 특징은 괄호의 짝을 맞추는 데 매우 유용합니다.

알고리즘의 핵심 아이디어

1. 스택 사용: 열린 괄호를 스택에 저장하고, 닫힌 괄호가 나올 때 스택에서 가장 최근의 열린 괄호를 꺼내어 짝이 맞는지 확인합니다.
2. 짝 확인: 닫힌 괄호가 나왔을 때 스택에서 꺼낸 열린 괄호와 짝이 맞지 않으면 유효하지 않은 문자열입니다.
3. 최종 확인: 문자열을 모두 처리한 후 스택이 비어 있어야 문자열이 유효합니다. 스택에 남은 열린 괄호가 있다면 이는 닫히지 않은 괄호가 있다는 뜻입니다.

코드의 주요 로직 설명

function isValid(s: string): boolean {
    const stack: string[] = [];
    const pair: Record<string, string> = {
        ')': '(',
        ']': '[',
        '}': '{',
    };

    for (const ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else {
            if (stack.pop() !== pair[ch]) {
                return false;
            }
        }
    }
    return stack.length === 0;
}

각 단계별 동작 과정

1. 스택과 매핑 객체 초기화:

   • stack: 열린 괄호를 저장할 스택입니다.
   • pair: 닫힌 괄호에 대응하는 열린 괄호를 매핑한 객체입니다.

2. 문자열 순회:

   • 문자열의 각 문자를 순회하면서 열린 괄호일 경우 스택에 추가합니다.
   • 닫힌 괄호일 경우 스택에서 가장 최근의 열린 괄호를 꺼내어(stack.pop()) 매핑 객체를 통해 짝이 맞는지 확인합니다.

3. 짝이 맞지 않을 경우:

   • stack.pop()의 결과가 현재 닫힌 괄호와 매핑된 열린 괄호와 다르면 false를 반환합니다.

4. 최종 결과 반환:

   • 문자열 순회가 끝난 후 스택이 비어 있으면 모든 열린 괄호가 짝을 이루었다는 뜻이므로 true를 반환합니다. 스택에 요소가 남아 있으면 false를 반환합니다.

핵심 변수들의 역할

• stack: 열린 괄호를 저장하여 나중에 닫힌 괄호와 짝을 맞추는 데 사용됩니다.
• pair: 닫힌 괄호와 매칭되는 열린 괄호를 저장하여 짝을 맞추는 데 사용됩니다.

왜 이 방법이 효과적인지

스택을 사용하면 열린 괄호를 나중에 닫힌 괄호와 짝을 맞출 때 가장 최근에 열린 괄호부터 확인할 수 있습니다. 이는 괄호의 중첩 구조를 처리하는 데 매우 적합합니다. 또한, 스택을 사용하여 문자열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)으로 매우 효율적입니다. 이 방법은 괄호의 짝을 맞추는 문제를 해결하는 데 최적의 접근 방식입니다.