[LeetCode] 22. Generate Parentheses

문제

LeetCode 22. Generate Parentheses

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

Generate Parentheses - LeetCode

언어

자바스크립트(JavaScript)

 

접근 방법

1. 재귀적으로 푼다.
2. (를 선택하는 경우와 )를 선택하는 경우로 나눈다.
3. 괄호 갯수를 초과했거나 유효하지 않은 경우는 거른다.

코드

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let result = [];
    comb(n, 0, 0, '', result);
    return result;
};

const comb = (n, leftNum, rightNum, str, result) => {
    if (leftNum === n && rightNum === n){
        if(check(str)){
            result.push(str);
        }
        return;
    }
    if(leftNum > n || rightNum > n){
        return;
    }
    comb(n, leftNum+1, rightNum, str + '(', result);
    comb(n, leftNum, rightNum+1, str + ')', result);
}

const check = (str) => {
    let status = [];
    let isInvalid = false;
    for (let i=0; i<str.length; i++){
        if(str[i] === '('){
            status.push('(');
        }else{
            if(status.pop() !== '('){
                isInvalid = true;
                break;
            }
        }
    }
    if(isInvalid){
        return false;
    }
    return true;
}

결과

Runtime: 80 ms, faster than 58.96% of JavaScript online submissions for Generate Parentheses.

Memory Usage: 42.3 MB, less than 13.48% of JavaScript online submissions for Generate Parentheses.

복기

1. 어렵지 않게 풀 수 있었다.
2. 재귀적으로 풀지 않으면 코드가 복잡해진다.