알고리즘
[프로그래머스] 올바른 괄호의 갯수
택시짱
2020. 2. 17. 17:54
링크
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개의 괄호쌍으로 [ (())
programmers.co.kr
풀이
올바른 괄호의 갯수를 찾는 문제이다.
올바른 괄호가 되기 위해서는 (의 갯수가 항상 )갯수보다 많거나 같아야 올바른 괄호가 될수 있다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#define SIZE 1010
using namespace std;
typedef long long int ll;
const int INF = 2000000000;
int res = 0;
void dfs(int left, int right, int cnt, int n) {
if (left < right || left > n || right > n)
return;
if (cnt == n * 2) {
res++;
return;
}
dfs(left + 1, right, cnt + 1, n);
dfs(left, right + 1, cnt + 1, n);
}
int solution(int n) {
dfs(1, 0, 1, n);
int answer = res;
return answer;
}
반응형