(javascript) 올바른 괄호의 갯수

코딩테스트 연습 - 올바른 괄호의 갯수 | 프로그래머스 스쿨

프로그래머스

 

 괄호를 보면 제일 먼저 떠오르는 스택. 하지만 이게 스택으로 푸는 문제가 맞나? 오히려 순열과 조합에 관한 문제로 보인다.

 가장 중요한 힌트는 n의 범위였다.

 n의 범위가 고작 1~14?

 이건 O(n!)으로 풀어도 되겠다.

 

 n개의 괄호를 가지고 만들 수 있는 모든 경우의 수를 구한다. -> n!

 그리고 만들어진 문자열이 올바른 문자열인지 확인한다.

 

 n개의 괄호를 가지고 문자열을 만드는 것은 n개의 상자에 n개의 공을 담는 방법의 수와 같다.

 그림으로 예시를 들어보았다.

 

 각 '('의 오른쪽에 빈 상자를 둔다.

 그리고 상자에 몇개의 공 ')'을 넣을지를 정한다.

 그러면 최종적인 문자열이 완성된다.

 그러나 전체 문자열을 만들 필요는 없고, 각 상자에 몇개의 공이 들어있는지만 확인하면 된다. (빨간색 배열)

 

 다음은 만들어진 문자열이 올바른 조건을 만족하는지를 검사해야한다.

 이건 스택을 이용했다.

 다만 스택 전체를 구현해서 진짜로 괄호를 넣고 빼는게 아닌, 스택에 있는 원소의 수만 계산한다.

 만약 스택의 크기가 0보다 작아진다면 올바른 문자열이 아니다.

 

코드

function solution(n) {
    var answer = 0;

    var a = new Array(n);
    a.fill(0);

    function foo(n, p, c, arr) {
        if (c === 0) {
            if (boo(arr)) {
                answer++;
            }
            return;
        }
        for (var i = p; i < n; i++) {
            arr[i]++;
            foo(n, i, c - 1, arr);
            arr[i]--;
        }
    }

    function boo(arr) {
        var stack = 0;
        for (var i = 0; i < arr.length; i++) {
            stack += 1 - arr[i];
            if (stack < 0) return false;
        }
        return true;
    }

    foo(n, 0, n, a);
    return answer;
}

결과

후기

 n의 범위를 보고 단순하게 풀어도 되겠구나, 생각은 했지만 더 세련되고 우아한 방법은 없을까 고민해보았다.

 괄호의 구조를 보면 트리와 같다는 생각이 들었다.

 이렇게 보면 괄호 안에 다른 괄호가 있는게 마치 노드의 자식으로 다른 노드가 있는것과 같다.

 이 아이디어에 착안해서 n+1개의 노드로 만들 수 있는 트리의 갯수를 구하면 어떨가 했지만... 생각해보니 오히려 어려운 풀이방식이 될것 같아서 그만뒀다.

 

 괄호 문자열을 만드는 함수 foo를 작성할때, 자꾸 파라미터가 하나씩 늘어나는게 마음에 안들었다. 처음에 foo(n, arr)로 작성했다가, 전체 상자의 갯수와 남은 공의 갯수를 분리하기 위해 남은 공의 갯수 c를 추가하고, foo(n, c, arr)에서 마지막으로 넣은 상자의 위치 p를 추가해서 foo(n, p, c, arr)가 됐다.