문제
풀이
n이 주어지면 n쌍의 가능한 모든 유효한 괄호들의 조합을 구하는 문제입니다. 재귀함수를 통해서 풀어주었습니다. 아래는 재귀함수의 코드입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// L : 고른 괄호의개수
// lCnt : '(' 를 고른 개수
// useable : ')' 를 고를 수 있는 개수
// s : 지금까지 만든 괄호
void setParenthesis(int L,int lCnt, int useable, string s){
// 완성된 괄호를 ans 벡터에 넣어주기
if(L == N*2){
ans.push_back(s);
return;
}
// 재귀 호출
if(useable>0)
setParenthesis(L+1, lCnt, useable-1, s+')');
if(lCnt<N)
setParenthesis(L+1, lCnt+1, useable+1, s+'(');
}
’)’는 반드시 ‘(‘가 나온 후에만 선택할 수 있기 때문에 useable 인자를 통해서 고를 수 있는 ‘)’의 개수를 세주었습니다.
만약 ‘(‘를 선택하면 useable은 1 증가하고 lCnt도 1증가 하게 되고,
1
2
// '(' 선택
setParenthesis(L+1, lCnt+1, useable+1, s+'(');
’)’를 선택한다면 useable만 1 감소하게 됩니다.
1
2
// ')' 선택
setParenthesis(L+1, lCnt, useable-1, s+')');
실행 결과로 속도는 아주 빨랐지만 메모리 사용량이 조금 많았습니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<string> ans;
int N;
void setParenthesis(int L,int lCnt, int useable, string s){
if(L == N*2){
ans.push_back(s);
return;
}
if(useable>0)
setParenthesis(L+1, lCnt, useable-1, s+')');
if(lCnt<N)
setParenthesis(L+1, lCnt+1, useable+1, s+'(');
}
vector<string> generateParenthesis(int n) {
N = n;
setParenthesis(0, 0, 0, "");
return ans;
}
};
