[프로그래머스/JS] 올바른 괄호의 갯수

[프로그래머스/JS] 올바른 괄호의 갯수

1. 문제

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

2. 제한사항

괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

3. 풀이

• DFS로 괄호의 경우의 수를 구해주고 해당 괄호가 올바른 괄호인지 확인해주었다.
• DFS를 해도 되겠다고 생각한 이유는 N 제한이 14여서 14C7이 3400정도여서 가능하다고 생각했다.
  근데 괄호 쌍이라 28C14긴한데 아무튼 통과했다.
• 괄호 쌍이기 때문에 2n개의 괄호 중에 여는 괄호의 위치 n개를 지정해주는 DFS 함수를 만들었다.
• n개를 선택한 후에는 해당 괄호가 올바른 괄호인지 확인하고 올바른 괄호라면 answer의 값을 추가했다.

4. 처음 코드와 달라진 점

• 올바른 괄호인지 확인하는 함수에서 for문 안에 조건문을 같은 레벨로 작성하였다.
• 수정 전

    function isCorrect() {
        let stack = [];
        for (const x of visited) {
            if (x) {
                stack.push(x);
            }
            else {
                if (!stack.length) return false;
                stack.pop();
            }
        }
        if (!stack.length) return true;
        else return false;
    }

• 수정 후

function isCorrect() {
        let stack = [];
        for (const x of visited) {
            if (x) stack.push(x);
            else if (stack.length) stack.pop();
            else return false;
        }
        
        return true;
    }

5. 코드

function solution(n) {
    let answer = 0;
    let visited = Array(n * 2).fill(0);
    
    function isCorrect() {
        let stack = [];
        for (const x of visited) {
            if (x) stack.push(x);
            else if (stack.length) stack.pop();
            else return false;
        }
        
        return true;
    }    
    
    
    function dfs(L, start) {
        if (L === n) {
            answer += isCorrect() ? 1 : 0;
        }
        else {
            for (let i = start; i < n * 2; i++) {
                visited[i] = 1;
                dfs(L + 1, i + 1);
                visited[i] = 0;
            }
        }
    }
    dfs(0, 0);
    return answer;
}