JavaScript로 유효한 괄호 문자열 만들기: 최소 대괄호 추가 문제 풀이

문제

JavaScript 함수를 작성해야 합니다. 이 함수는 오직 '[' 또는 ']' 문자로만 구성된 문자열 str을 입력받습니다.

함수의 목표는 대괄호('[' 또는 ']')를 임의의 위치에 최소한으로 추가하여, 결과적으로 만들어지는 괄호 조합 문자열이 유효(균형 잡힌)하도록 만드는 것입니다. 마지막에는 추가해야 하는 대괄호의 최소 개수를 반환하면 됩니다.

예를 들어 함수의 입력이 다음과 같다면,

입력

const str = '[]]';

출력

const output = 1;

출력 설명

문자열 맨 앞에 '['를 한 개 추가하면 '[[]]'이 되어 균형 잡힌 문자열이 되기 때문입니다.

접근 방식 및 코드

이 문제는 별도의 스택 자료구조 없이 두 개의 카운터 변수만 사용하여 선형 시간(O(n)) 안에 해결할 수 있습니다.

• left: 아직 짝을 찾지 못한 여는 괄호 '['의 개수
• right: 짝을 찾지 못해 새로운 '['가 필요한 닫힌 괄호 ']'의 개수

문자열을 처음부터 끝까지 순회하며 다음 규칙을 적용합니다.

1. '['를 만나면 left 값을 1 증가시킵니다.
2. ']'를 만나면 left가 0보다 클 경우 left를 1 감소시켜 짝을 맞추고, 그렇지 않으면 right를 1 증가시켜 앞에 추가해야 할 '['의 개수를 기록합니다.

순회가 끝난 후 left + right 값이 곧 추가해야 하는 최소 대괄호 개수입니다. 남은 left 값은 문자열 뒤에 붙여 주어야 할 ']'의 개수를 의미합니다.

const findAdditions = (str = '') => {
    let left = 0;
    let right = 0;
    for (let i = 0; i < str.length; i++) {
        if (str[i] === '[') {
            left += 1;
        } else if (str[i] === ']') {
            if (left > 0) {
                left -= 1;
            } else {
                right += 1;
            }
        }
    }
    return left + right;
};
console.log(findAdditions(str));

출력

1

이 알고리즘은 문자열 길이를 n이라 할 때 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적이며, 괄호 검증 유형 문제에서 널리 활용되는 패턴입니다.