프로그래머스 - 올바른 괄호의 갯수(Level 4)/Wanna Be 컴잘알

문제 출처 - https://programmers.co.kr/learn/courses/30/lessons/12929?language=cpp#

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

 

-문제-

 

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

 

제한사항

 

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

---

입출력 예

 

n	result
2	2
3	5

입출력 예 설명

 

입출력 예 #1

2개의 괄호쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다.

입출력 예 #2

3개의 괄호쌍으로 [ ((())), (()()), (())(), ()(()), ()()() ]의 5가지를 만들 수 있습니다.

 

-접근-

 

1. vector<int>에 넣는 괄호의 순서를 여는괄호 '(' = 1 , 닫는괄호 ')' = -1이라고 생각하고 넣어 놓고 중복 없는 순열을 구한 뒤, 각 수열마다 앞에서 부터 순차적으로 더하다가 그 값이 음수라면 잘못된 괄호이고 그 값이 양수라면 옳은 괄호라고 생각하면 된다.

 

2. 처음에 접근 할 때 재귀 함수와 set자료구조를 사용한 중복없는 순열으로 풀려고 하였는데, set자료구조를 사용하니까 아무래도 거의 순열에 가까운 횟수를 반복하다보니 답은 구해지지만 일부 케이스에서 시간초과가 발생하였다. 

(참고 : 시간 초과 코드1)

=> 중복된 순열을 구하고 그 수열들을 set자료구조에 넣어 중복되지 않은 갯수를 구함.

 

3. 다음은 next_permutation이라는 algorithm라이브러리에 속한 순열함수를 사용해보았다. next_permutation을 사용하면 중복없는 순열을 구할 수 있다. (참고: 정답 코드1)

 

 

-코드-

 

시간 초과 코드1

#include <string>
#include <vector>
#include <iostream>
#include <set>

using namespace std;

int dp[15];
int answer = 0;
vector <int> v;
vector <int> input;
set <vector<int>> s;
bool check[15];

void solve(int cnt, int n, int sum) {
	if (sum < 0) {
		return;
	}
	if (cnt == n*2 ) {
		s.insert(v);
		return;
	}
	for (int k = 0; k < input.size(); k++) {
		if (check[k] == false) {
			check[k] = true;
			v.push_back(input[k]);
			sum += input[k];
			solve(cnt + 1, n, sum);
			sum -= input[k];
			v.pop_back();
			check[k] = false;
		}
	}
}

int solution(int n) {
	for (int i = 0; i < n; i++) {
		input.push_back(1);
		input.push_back(-1);
	}
	solve(0, n, 0);
	
	answer = s.size();
	return answer;
}

 

정답 코드 1

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;

bool vectorSum(vector<int> vv){
    int sum=0;
    for(int i=0; i<vv.size();i++){
        sum += vv[i];
        if(sum<0)
            return false;
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    for(int i=0; i<n;i++){
        v.push_back(1);
        v.push_back(-1);
    }
    
    do{
        if(vectorSum(v))
            answer+=1;
    }while(next_permutation(v.begin(),v.end()));
    
    return answer;
}