[프로그래머스] - "괄호 변환" C++ / 재귀 / stack

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60058

프로그래머스

 

풀이과정

# 해석

'(' 과 ')' 두가지 문자로만 이루어진 문자열이 주어졌을 때, 올바른 괄호 문자열로 바꿔서 반환하는 것이 목적입니다.

그리고 올바른 괄호 문자열로 변환하는 알고리즘은 문제에서 다음과 같이 주어졌습니다.

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. 생성된 문자열을 반환합니다.

고려해야 할 점은

1. 문자열의 종류에는 "균형잡힌 괄호 문자열" / "올바른 괄호 문자열" 두가지가 존재합니다.

1-1. "균형잡힌 괄호 문자열" 의 경우 '(' 의 개수와 ')' 의 개수가 동일한 경우이며 ex) "))(())(("

1-2. "올바른 괄호 문자열" 의 경우 개수 뿐만 아니라 짝이 모두 맞는 경우입니다. ex) "(())()"

 

# 풀이

1. 먼저 위 알고리즘의 2번 과정에서 문자열을 "균형잡힌 괄호 문자열" 2개로 나누어야 하기 때문에

아래와 같은 함수가 작성되었습니다.

int dividing(string s) {
	int cnt1 = 0, cnt2 = 0;
	for(int i=0; i<s.size(); i++) {
		if(s[i] == '(') cnt1++;
		else cnt2++;
		if(cnt1 == cnt2) return i;
	}
}

문자열을 순회하면서 '('과 ')'의 개수가 같아지는 첫 시점이 문자열 u,v로 나누어지는 시점입니다.

왜냐하면 조건에서 문자열 u는 더이상 나누어지지 않아야 한다고 했기 때문입니다.

 

나눌 인덱스를 찾았으면 아래와 같이 분할합니다.

// 2. 문자열 분할
string u,v;
int idx = dividing(s);
u = s.substr(0,idx+1);
v = s.substr(idx+1);

 

2. "올바른 괄호 문자열" 인지 판별하기 위해 stack을 이용합니다.

'()' 한쌍이 전부 이루어져서 마지막에 stack이 비어있다면 올바른 괄호 문자열이 됩니다.

bool checking(string s) {
	stack <char> st;
	for(int i=0; i<s.size(); i++) {
		if(st.empty()) st.push(s[i]);
		else if(st.top() == '(' && s[i] == ')') st.pop();
		else st.push(s[i]);
	}
	if(st.size() != 0) return false;
	else return true;
}

 

3. 이제 주어진 알고리즘 조건에 따라 반복하기만 하면 됩니다. 

string dfs(string s) {
	// 1. 빈 문자인지 체크
	if(s.size() == 0) return "";
	// 2. 문자열 분할
	string u,v;
	int idx = dividing(s);
	u = s.substr(0,idx+1);
	v = s.substr(idx+1);

	// 3. u가 올바른 괄호 문자열이라면 v에 대해 1단계부터 시작
	// 3-1. 결과를 u에 붙여서 반환
	if(checking(u)) return u += dfs(v);
	// 4. u가 올바른 괄호 문자열이 아니면 문자열 생성해서 반환
	else {
		string temp = "(";
		temp += dfs(v);
		temp += ")";
		// u의 첫번째,마지막을 제거하고 뒤집은 결과 붙이기
		if(u.size() > 2) for(int i=1; i<u.size()-1; i++) temp += (u[i] == '(') ? ')' : '(';
		
		return temp;
	}
}

 

전체 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

bool checking(string s) {
	stack <char> st;
	for(int i=0; i<s.size(); i++) {
		if(st.empty()) st.push(s[i]);
		else if(st.top() == '(' && s[i] == ')') st.pop();
		else st.push(s[i]);
	}
	if(st.size() != 0) return false;
	else return true;
}

int dividing(string s) {
	int cnt1 = 0, cnt2 = 0;
	for(int i=0; i<s.size(); i++) {
		if(s[i] == '(') cnt1++;
		else cnt2++;
		if(cnt1 == cnt2) return i;
	}
}

string dfs(string s) {
	// 1. 빈 문자인지 체크
	if(s.size() == 0) return "";
	// 2. 문자열 분할
	string u,v;
	int idx = dividing(s);
	u = s.substr(0,idx+1);
	v = s.substr(idx+1);

	// 3. u가 올바른 괄호 문자열이라면 v에 대해 1단계부터 시작
	// 3-1. 결과를 u에 붙여서 반환
	if(checking(u)) return u += dfs(v);
	// 4. u가 올바른 괄호 문자열이 아니면 문자열 생성해서 반환
	else {
		string temp = "(";
		temp += dfs(v);
		temp += ")";
		// u의 첫번째,마지막을 제거하고 뒤집은 결과 붙이기
		if(u.size() > 2) for(int i=1; i<u.size()-1; i++) temp += (u[i] == '(') ? ')' : '(';
		
		return temp;
	}
}

string solution(string p) {
    string answer = "";
	if(checking(p)) return p;
	answer = dfs(p);
    return answer;
}