괄호 변환
프로그래머스 괄호 변환 풀이
문제설명
’(‘ 와 ’)’ 로만 이루어진 문자열이 있을 경우, ‘(‘ 의 개수와 ‘)’ 의 개수가 같다면 이를 균형잡힌 괄호 문자열
이라고 부릅니다.
그리고 여기에 ‘(‘와 ‘)’의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열
이라고 부릅니다.
예를 들어, "(()))("
와 같은 문자열은 “균형잡힌 괄호 문자열” 이지만 “올바른 괄호 문자열”은 아닙니다.
반면에 "(())()"
와 같은 문자열은 “균형잡힌 괄호 문자열” 이면서 동시에 “올바른 괄호 문자열” 입니다.
’(‘ 와 ‘)’ 로만 이루어진 문자열 w가 “균형잡힌 괄호 문자열” 이라면 다음과 같은 과정을 통해 “올바른 괄호 문자열”로 변환할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.`
“균형잡힌 괄호 문자열” p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 “올바른 괄호 문자열”로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 문자열의 길이 ≤ 1,000
- 입력 문자열은 균형잡힌 괄호 문자열이다. 즉, ‘(’와 ‘)’의 개수는 같다.
해결과정
길이가 1,000이므로 $O(S^3)$이어도 넉넉하게 풀 수 있다. 해당 문제는 구체적으로 어떻게 해야하는지 서술되어있어서, 그대로 구현했다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
vector<string> splitUV(string& in){ // v[0] = U, v[1] = V
string u;
string v;
int l = 0, r = 0;
int ssize = in.size();
for(int i = 0; i<ssize; i++){
if(in[i] == '('){
l++;
}
else{
r++;
}
if(l == r){
u = in.substr(0, i + 1);
if(i + 1 != ssize){
v = in.substr(i + 1);
}
break;
}
}
return {u, v};
}
//
bool checkcorrect(string& in){
int l = 0;
int r = 0;
for(char& a : in){
if(a == '('){
l++;
}
else{
r++;
if(r > l) return false;
}
}
if(l != r) return false;
return true;
}
string convert(string& w){
if(w.empty() || checkcorrect(w)) return w;
// uv 분리
vector<string> vec = splitUV(w);
string u = vec[0];
string v = vec[1];
cout << u << ' ' << v << '\n';
string res;
if(checkcorrect(u)){
return res = u + convert(v);
}
res.push_back('(');
res += convert(v);
res.push_back(')');
u.pop_back();
u.erase(0,1);
for(int i = 0; i<u.size();i++){
if(u[i] == '('){
u[i] = ')';
}
else u[i] = '(';
}
res += u;
return res;
}
string solution(string p) {
return convert(p);
}
This post is licensed under CC BY 4.0 by the author.