[Programmers] 괄호 변환

✔️ 문제 링크

◾ 2020 카카오 블라인드 채용 기출 문제이다.

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

코딩테스트 연습 - 괄호 변환

---

✔️ 문제 이해

◾ '(' 와 ')' 로만 이루어진 문자열이 주어진다.

◾ '(' 의 개수와 ')' 의 개수가 같고,  '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이는 올바른 괄호 문자열이다.

◾ 문자열이 주어졌을 때 올바른 괄호 문자열로 변환해서 반환하면 된다. 

---

✔️ 설계

◾ 이 문제는 내가 설계할 필요가 없다. 문제에서 친철하게 올바른 괄호 문자열을 만드는 알고리즘을 알려준다.

◾ 알고리즘을 보고 그대로 구현하면 된다. 아래 소스 코드의 주석은 문제에서 주어진 알고리즘을 그대로 적은 것이다. 

---

👨🏻‍💻 소스 코드

#include <string>
#include <vector>
#include<stack>
using namespace std;

bool isRigt(string s) { // 인자 s가 올바른 문자열인지 판별해준다. 
	stack<char> st;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ')') {
			if (!st.empty() && st.top() == '(')
				st.pop();
			else
				st.push(s[i]);
		}
		else {
			st.push(s[i]);
		}
	}

	if (st.empty())
		return true;
	else
		return false;
}

string solve(string w) {
	if (w == "") return ""; // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
	
	string u, v;
	stack<char> st;
	int idx;

	// 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
	// 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, 
	// v는 빈 문자열이 될 수 있습니다.
	int left = 0, right = 0;

	for (int i = 0; w.size(); i++) {
		if (w[i] == '(') left++;
		else if (w[i] == ')') right++;

		if (left != 0 && right != 0) {
			if (left == right) {
				idx = i;
				break;
			}
		}
	}

	u = w.substr(0, idx+1);
	v = w.substr(idx + 1);

	// 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
	if (isRigt(u)) 
		return u + solve(v); // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
	else{ // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
		
		string tmp = "("; // 4 - 1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
		// 4 - 2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
		tmp += solve(v); 
		tmp += ")"; // 4-3. ')'를 다시 붙입니다.

		string newU = "";
		// 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
		for (int i = 1; i < u.size()-1; i++) {
			if (u[i] == '(')
				newU += ")";
			else
				newU += "(";
		}
		return tmp + newU; // 4-5. 생성된 문자열을 반환합니다.
	}
}

string solution(string p) {
	string answer = "";
	answer = solve(p);
	return answer;
}

---

✔️ 문제 회고

◾ 처음에 어려운 문제인줄 알았지만, 문제에서 주어진 알고리즘을 그대로 구현하니까 쉽게 풀렸다.

◾ 문자열을 다루는 문제, stack 활용이 필요한 괄호쌍 문제에 대해 더 익숙 해져야겠다고 느꼈다.