https://programmers.co.kr/learn/courses/30/lessons/60058
코딩테스트 연습 - 괄호 변환 | 프로그래머스
카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는
programmers.co.kr
문제가 복잡해 보이지만 정말 시키는 대로만 재귀로 잘 구현하면 된다. 재귀로 구현해야하는 부분도 문제에 잘 나와있다.
올바른 괄호 문자열인지 검사하는 부분만 스택을 이용해서 따로 구현했다.
문자열의 모든 문자들에 대해서 여는 괄호면 스택에 넣어주고 닫는 괄호면 스택에서 빼준다. 이때, 스택이 비어있다면 올바른 괄호 문자열이 아니므로 false를 바로 리턴한다.
문자열 검사가 끝났는데 스택에 아직 괄호가 남아있다면 그것도 올바른 괄호 문자열이 아니므로 false를 리턴한다.
위에서 false를 리턴하지 않았다면 올바른 괄호 문자열이므로 true를 리턴한다.
각 조건을 구현한 부분에 주석을 달아놨다.
|
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <string>
#include <vector>
#include <stack>
using namespace std;
//올바른 괄호 문자열인지 검사
bool isok(string s) {
stack<char> st;
for (char c : s) {
if (c == '(') {
st.push(c);
}
else if (c == ')') {
if (st.empty()) {
return false;
}
else {
st.pop();
}
}
}
if (st.empty()) return true;
else return false;
}
string seperate(string p) {
if (p == "") return "";
string u = "";
string v = "";
string result = "";
int cnt1 = 0;
int cnt2 = 0;
int index = 0;
//2번 조건
for (char c : p) {
if (c == '(') {
cnt1++;
}
else {
cnt2++;
}
index++;
//균형잡힌 상태가 되면 바로 break(더 분리할 수 없도록);
if (cnt1 == cnt2) break;
}
//u와 v로 나누다.
u += p.substr(0, index);
v += p.substr(index);
//3번 조건
if (isok(u)) {
result += u;
result += seperate(v);
}
else {
//4번 조건
//4-1
result = "(";
//4-2
result += seperate(v);
//4-3
result += ")";
//4-4
u = u.substr(1, u.size() - 2);
int len = u.size();
for (int i = 0; i<len; i++) {
if (u[i] == '(') {
result += ")";
}
else {
result += "(";
}
}
}
//4-5
return result;
}
string solution(string p) {
string answer = "";
//1번 조건
if (isok(p)) return p;
answer = seperate(p);
return answer;
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++ (1) | 2020.03.11 |
|---|---|
| 프로그래머스 [2020카카오공채] 블록 이동하기 c++ (2) | 2020.02.14 |
| 프로그래머스 [2020카카오공채] 문자열 압축 c++ (0) | 2019.10.17 |
| 프로그래머스 - 소수 찾기 (0) | 2019.10.04 |
| 프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 프렌즈4블록 c++ (0) | 2019.08.29 |
