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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12929

접근 방법

1. 순열 & 스택

n값의 범위가 작아서 가능했던 것 같다.

1. 괄호의 개수로 만들 수 있는 모든 문자열을 순열을 이용해 구한 후
2. 스택을 이용해 올바른 괄호인지 판단한다.

2. DP

찾아보니 DP를 이용하여 다들 푸셨다.
카탈란 수의 일종이라고 한다.

왼쪽 끝에 한 쌍의 () 괄호를 두고, 이 괄호의 안과 밖을 생각해서 계산
ex. C4 를 구하기
1단계. 왼쪽 끝 한 쌍의 괄호 () 안에는 없고, 오른쪽에 괄호 3쌍 두기
() {3쌍의 괄호} = 경우의 수 C0*C3

2단계. 왼쪽 끝 한 쌍의 괄호 () 안에 1쌍의 괄호를 넣고, 오른쪽에 2쌍 두기
({1쌍의 괄호}) {2쌍의 괄호} = 경우의 수 C1*C2

3단계. 왼쪽 끝 한 쌍의 괄호 () 안에 2쌍의 괄호를 넣고, 오른쪽에 1쌍 두기
({2쌍의 괄호}) {1쌍의 괄호} = 경우의 수 C2*C1

4단계. 왼쪽 끝 한 쌍의 괄호 () 안에 3쌍의 괄호를 넣고, 오른쪽에 0쌍 두기
({3쌍의 괄호}) = 경우의 수 C3*C0

결론적으로 C4 = C0C3 + C1C2 + C2C1 + C3C0 = 5+2+2+5 = 14

풀이

1. 순열 & 스택

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

vector<char> charVec;

bool IsRightGwalho()
{
    stack<char> ss;
    
    for(char ch : charVec)
    {
        if (ss.empty()) 
            ss.push(ch);
        else
        {
            if (ss.top() == '(' && ch == ')')   
                ss.pop();
            else
                ss.push(ch);
        }
    }
    
    return ss.empty();
}
int solution(int n) {
    int answer = 0;
    
    // 0. base가 되는 문자열 생성
    
    for(int i=0; i<n; i++)
    {
        charVec.push_back('(');
        charVec.push_back(')');
    }
    
    
    // 정렬
    sort(charVec.begin(), charVec.end());
    
    // 1. 순열 구하기 
    do
    {
        // 2. 올바른 괄호인지 check 
        if (IsRightGwalho())
            answer++;
            
    }while(next_permutation(charVec.begin(), charVec.end()));
    
    
    return answer;
}

2. DP

#include <string>
#include <vector>

using namespace std;

int dp[15];


int solution(int n) {
    
    int answer = 0;
   
    dp[0] = 1;
    dp[1] = 1;
    
    for(int i=2; i<=n; i++)
    {        
        int mmax = i-1;
        
        for(int j=0; j<=mmax; j++)
        {
             dp[i] += dp[mmax-j] * dp[j];
        }
    }
    return dp[n];
}

정리

위 ) dp
아래 ) 순열

시간차이 ㄷㄷ .. 애초에 n이 컸으면 순열은 통과 못했을 수도 있다.

참고

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