JavaScript에서 대괄호 문자열 점수 계산하기

문제 설명

균형 잡힌(balanced) 대괄호 문자열 str을 첫 번째이자 유일한 인자로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

함수는 아래 규칙에 따라 문자열의 점수를 계산한 뒤 반환해야 합니다.

• []의 점수는 1입니다.

• AB의 점수는 A + B입니다. 단, A와 B는 각각 균형 잡힌 괄호 문자열이어야 합니다.

• [A]의 점수는 2 × A입니다. 단, A는 균형 잡힌 괄호 문자열이어야 합니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const str = '[][]';

출력

const output = 2;

'[][]'는 두 개의 독립된 []가 나란히 이어진 형태이므로, 각각 1점씩 더해 최종 점수는 2가 됩니다.

풀이 코드

다음은 이 문제를 해결하는 전체 코드입니다.

const findScore = (str = '') => {
    const arr = [];
    for (const char of str) {
        arr.push(char);
        while (arr[arr.length - 1] === ']') {
            arr.pop();
            if (arr[arr.length - 1] === '[') {
                arr.pop();
                arr.push(1);
            } else {
                let num = arr.pop();
                while (arr[arr.length - 1] >= 1) {
                    num += arr.pop();
                }
                arr.pop();
                arr.push(2 * num);
            }
        }
    }
    return arr.reduce((acc, a) => acc + a, 0);
};
console.log(findScore(str));

출력 결과

2

동작 원리

이 풀이의 핵심은 스택(Stack) 자료구조를 활용하는 것입니다. 동작 과정을 살펴보면 다음과 같습니다.

• 문자열을 한 글자씩 순회하며 배열(스택)에 push합니다.

• 닫는 대괄호 ']'를 만나면 스택에서 요소를 하나 꺼냅니다(pop).

• 그 직전 요소가 여는 대괄호 '['라면 빈 쌍 []이므로 점수 1을 스택에 push합니다.

• 그렇지 않고 숫자가 나온다면 내부에 이미 계산된 점수가 있다는 뜻이므로, 연속된 숫자들을 모두 합산한 뒤 여는 대괄호를 제거하고 그 값에 2를 곱해 다시 push합니다. 이는 규칙 [A] = 2 × A를 반영한 것입니다.

• 모든 문자를 처리한 후에는 스택에 남아 있는 점수들을 모두 더해 최종 결과를 반환합니다. 이 과정이 규칙 AB = A + B를 자연스럽게 처리해 줍니다.

이처럼 스택 기반 접근 방식을 사용하면 중첩된 대괄호 구조도 재귀 호출 없이 깔끔하게 처리할 수 있으며, 시간 복잡도는 O(n)으로 효율적입니다.