[LeetCode] Generate Parentheses (javascript)

가능한 모든 괄호 조합을 중복없이 리턴하는 문제이다.

 

유효한 괄호조합 판별(Valid Parentheses) + 조합 같은 느낌의 문제이다.

굉장히 까다로울 걸로 생각했으나, Valid Parentheses 문제를 풀어봤다면(유효한 괄호조합 판별법을 안다면)

크게 어렵지 않았다.

(Valid Parentheses 문제 : https://leetcode.com/problems/valid-parentheses/)

 

유효한지 확인하는 방법은 스택을 활용하면 된다.

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    if (n === 1) return ['()'];

    let result = ['(']; // ')'로 시작하는 정상적인 괄호는 존재하지 않음

    for (let i = 0; i < n * 2 - 1; i++) {
        result = addPair(result, n);
    }

    const arr = [...new Set(result)].sort();
    const answer = arr.filter((a) => isValid(a));
    return answer;
};

const addPair = (pairArr, n) => {
    const result = [];
    for (let pair of pairArr) {
        if (isBalanced(pair, n)) {
            result.push(`${pair}(`, `${pair})`);
        }
    }
    return result;
};

// ( 또는 )가 n개 이상이면 이미 균형이 깨진 괄호로 판단하는 함수
const isBalanced = (pair, n) => {
    const lefts = [...pair].filter((p) => p == '(');
    return lefts.length < n + 1 && pair.length - lefts.length < n + 1;
};

// '('는 스택에 집어넣고, ')'가 들어오면 스택에서 '('를 제거하는 방식으로
// 유효성을 검증하는 함수
const isValid = (str) => {
    const stack = [];
    for (let i = 0; i < str.length; i++) {
        if (str[i] === '(') {
            stack.push('(');
        } else {
            if (stack[stack.length - 1] === '(') {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};

 

 

https://leetcode.com/problems/generate-parentheses/