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

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

 

문제 설명

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

 

제한사항

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

---

C++ 풀이

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

using namespace std;

int solution(int n) {
	int answer = 0;
	int sum = 0;
	vector <int> s;
	for (int i = 0; i < n; i++) {
		s.push_back(1); //왼 괄호의 값 1
		s.push_back(-1); //오른 괄호의 값 1
	}
	do {
		sum = 0;
		answer++;
		for (int i = 0; i < 2*n; i++) {
			sum += s[i];
			if (sum < 0) { //한 번이라도 오른 괄호가 왼 괄호보다 많아지면 틀린 괄호 표현이다
				answer--;
				break;
			}	
		}
	} while (next_permutation(s.begin(), s.end())); //만들 수 있는 괄호 조합
	return answer;
}

처음 실행 후, 괄호쌍의 개수를 받아 int벡터에 괄호 값을 넣었다.

예를 들어 n = 3인 경우 기본 타입인 ()()()을 1, -1, 1, -1, 1, -1와 같이 정수로 변환하여 벡터에 넣었다.

 

이후, 모든 괄호 조합을 만드는 과정에서,

한 번이라도 오른 괄호 가 왼 괄호보다 많아지는 순간(합이 음수인 경우)이 있으면 그 조합은 틀린 괄호 조합으로 처리하였다.

 

EX. 아래 조합의 경우 세번째 괄호를 확인하면 바로 틀린 괄호 조합임을 알 수 있다.

( ) ) ( ( )

 

 

문제 링크

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

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