[JS 알고리즘] 괄호문자제거 문제 풀이 – 스택과 카운트 방식 비교

• 문제
• 내가 푼 풀이
• 해답
• 풀이 방법 비교
• 어떤 풀이가 더 좋은가
• FAQ

문제

입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 남은 문자만 출력하는 프로그램을 작성하세요.

입력설명
첫 줄에 문자열이 주어진다. 문자열의 길이는 100을 넘지 않는다.

출력설명
남은 문자만 출력한다.

입력예제 1
(A(BC)D)EF(G(H)(IJ)K)LM(N)

출력예제 1
EFLM

내가 푼 풀이

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

문자열을 왼쪽부터 오른쪽으로 하나씩 순회하면서, 여는 괄호 ‘(‘를 만나면 카운트를 증가시키고 닫는 괄호 ‘)’를 만나면 카운트를 감소시킵니다. 카운트 값이 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) {
    let answer;
    let stack = [];
    for (let x of s) {
        if (x === ')') {
            while (stack.pop() !== '(');
        }
        else stack.push(x);
    }
    answer = stack.join('');
    return answer;
}

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

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

풀이 방법 비교

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

구분	특징
카운트 방식	간결한 코드, 낮은 메모리 사용, 빠른 구현
스택 방식	괄호 구조 명확, 다양한 문제로 확장 가능

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

어떤 풀이가 더 좋은가

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

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

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

FAQ

Q. 괄호가 여러 단계로 중첩되어도 카운트 방식이 안전한가요?
네, 여는 괄호와 닫는 괄호의 개수만 정확히 맞는 입력이라면 중첩 깊이와 관계없이 올바르게 동작합니다.

Q. 스택 방식이 더 많이 사용되는 이유는 무엇인가요?
괄호 관련 문제 대부분이 스택 구조로 일반화할 수 있기 때문에, 다양한 유형에 재사용할 수 있다는 장점이 있습니다.

Q. 실무 코드에서도 이런 풀이가 사용되나요?
실무에서는 문자열 파싱, 수식 처리, 템플릿 엔진 구현 등에서 유사한 개념이 활용되며, 특히 스택 사고 방식은 매우 중요하게 사용됩니다.