코딩테스트 스택 풀이: 괄호문자 제거하기

내가 푼 풀이

내가 푼 풀이는 괄호문자제거 문제를 “현재 문자가 괄호 안에 있는지, 괄호 밖에 있는지”라는 상태 판단 문제로 해석한 방식입니다. 이 풀이는 스택 자료구조를 사용하지 않고, 괄호의 개수를 세는 카운트 변수 하나로 문제를 해결합니다.

문자열을 왼쪽부터 오른쪽으로 하나씩 순회하면서, 여는 괄호 ‘(‘를 만나면 카운트를 증가시키고 닫는 괄호 ‘)’를 만나면 카운트를 감소시킵니다. 카운트 값이 0이라는 의미는 현재 위치가 괄호 밖이라는 뜻이며, 이때만 문자를 결과 배열에 추가합니다.

반대로 카운트 값이 1 이상이라면 현재 문자는 괄호 내부에 있으므로 무시됩니다. 이 방식은 중첩 괄호가 몇 단계로 들어가더라도 카운트 값만 정확히 관리되면 문제없이 동작합니다.

function solution(s) {
    let answer = [];
    let count = 0;
    for (let x of s) {
        if (x === "(") {
            count++;
        } else if (x === ")" && count > 0) {
            count--;
        } else if (count === 0) {
            answer.push(x);
        }
    }
    return answer.join('');
}

let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str));

이 풀이의 가장 큰 장점은 코드가 매우 간결하고 직관적이라는 점입니다. 스택을 사용하지 않기 때문에 메모리 사용이 최소화되며, 문자열을 한 번만 순회하므로 시간 복잡도 또한 O(N)으로 효율적입니다.

다만 이 방식은 괄호 구조 자체를 명시적으로 표현하지 않기 때문에, 괄호 내부의 실제 문자 구성이 중요한 문제에는 그대로 적용하기 어렵다는 한계가 있습니다.

해답

정답 풀이는 괄호문자제거 문제를 스택(Stack)을 활용한 전형적인 문자열 처리 문제로 접근합니다. 이 방식은 괄호 구조를 직접 자료구조로 표현하며, 괄호 내부 문자를 실제로 제거하는 과정을 거칩니다.

문자열을 순회하면서 문자를 하나씩 스택에 저장하다가, 닫는 괄호 ‘)’를 만나면 여는 괄호 ‘(‘가 나올 때까지 스택에서 문자를 제거합니다. 이 과정에서 괄호 내부에 있던 문자와 괄호 자체가 모두 제거됩니다.

모든 문자열 처리가 끝난 후, 스택에 남아 있는 문자들만 이어 붙이면 괄호 밖 문자만으로 구성된 최종 문자열을 얻을 수 있습니다.

function solution(s) {
    const stack = [];

    for (const x of s) {
        if (x !== ')') {
            stack.push(x);
            continue;
        }

        while (stack.length > 0 && stack[stack.length - 1] !== '(') {
            stack.pop();
        }
        if (stack.length === 0) {
            throw new Error('대응하는 여는 괄호가 없습니다.');
        }
        stack.pop();
    }

    if (stack.includes('(')) {
        throw new Error('닫히지 않은 여는 괄호가 있습니다.');
    }
    return stack.join('');
}

let str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)";
console.log(solution(str));

이 풀이는 괄호문제 전반에 매우 강력하게 적용할 수 있는 구조입니다. 중첩 괄호, 문자열 압축, 수식 계산 등 다양한 유형으로 확장이 가능하며, 괄호 문제의 정석적인 사고 방식을 학습하는 데 큰 도움이 됩니다.

풀이 방법 비교

두 풀이는 모두 괄호문자제거 문제를 해결할 수 있으며, 시간 복잡도는 O(N)으로 동일합니다. 그러나 문제를 바라보는 관점과 코드의 성격에는 분명한 차이가 있습니다.

카운트 방식은 괄호 내부 여부만 판단하면 되는 문제에서 매우 효율적이며, 스택 방식은 괄호 구조 자체를 다뤄야 하는 문제에서 강력합니다.

어떤 풀이가 더 좋은가

코딩 테스트 관점에서는 문제의 의도를 빠르게 파악하는 것이 중요합니다. 괄호문자제거처럼 단순히 괄호 내부를 제거하는 문제라면 카운트 방식이 더 빠르고 깔끔한 선택이 될 수 있습니다.

반면 괄호의 짝 검증, 중첩 구조 분석, 수식 계산 등으로 확장될 가능성이 있다면 스택 풀이를 선택하는 것이 장기적으로 더 좋은 판단입니다.

학습 목적이라면 두 방식을 모두 이해하고, 문제 유형에 따라 적절한 접근 방식을 선택할 수 있는 판단력을 기르는 것이 가장 중요합니다.

괄호 판단을 넓히려면 JavaScript 올바른 괄호 스택 검증으로도 이어서 봐두면 도움이 됩니다.

괄호 구조 해석을 더 확장하려면 JS 쇠막대기 스택 레이저 절단 문제도 함께 비교해보세요.

유효 입력·복잡도·안전성 검증

카운터 풀이는 현재 깊이가 0일 때만 문자를 결과에 넣으므로 추가 작업 공간이 결과 배열을 제외하면 O(1)입니다. 스택 풀이는 괄호 밖 문자까지 보관하므로 최악 O(N)의 공간을 사용합니다. 두 방식 모두 각 문자를 넣고 빼는 횟수가 제한되어 전체 시간은 O(N)입니다.

기존의 while (stack.pop() !== '('); 형태는 닫는 괄호에 대응하는 여는 괄호가 없으면 pop()이 계속 undefined를 반환해 종료하지 않습니다. 수정 코드에는 스택 길이 검사를 넣고, 잘못된 입력이면 조용히 결과를 만들지 않고 오류를 내도록 했습니다. 배열 끝에 값을 넣는 push()와 마지막 값을 제거해 반환하는 pop()의 정확한 동작은 MDN push()와 pop() 문서를 기준으로 확인할 수 있습니다.

console.assert(solution('(A(BC)D)EF') === 'EF');
console.assert(solution('ABC') === 'ABC');
// solution('A)B')는 대응하는 여는 괄호가 없어 오류를 냅니다.

문제에서 항상 올바른 괄호 문자열만 준다면 간단한 카운터 풀이로 충분합니다. 입력 유효성까지 책임지는 함수라면 닫는 괄호에서 깊이가 음수가 되는지, 순회가 끝난 뒤 깊이가 0인지도 검사해야 합니다.

정리: ‘괄호 안 문자를 버린다’는 목적에는 카운터가 간단하고, 실제 문자를 되돌아가며 제거하거나 여러 구조로 확장할 때는 스택이 유용합니다. 어느 쪽이든 입력 전제와 실패 동작을 먼저 문서화하세요.