[programmers] 60058번 - 괄호 변환(재귀함수, 2020 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제 

 

 지문 그대로 구현하면 됐다. 오히려 지문을 이해하면서 시간이 조금 오래 걸린 문제였다.

---

 

프로그래머스

---

2. 풀이

 

 문제를 쪼개는 것보다는 그냥 각 기능을 하는 함수를 이번 단원에서는 소개하는 것이 훨씬 효율적이라고 생각한다.

 

- get_uv()

 

 해당 함수는 u와 v를 분리하는 함수이다. 여는 괄호와 닫는 괄화의 갯수가 항상 같기에, 간단하게 각 괄호의 수만을 count하는 방식으로 함수를 구현했다. 클린 코드를 만들어보고 싶어서 vector<string>을 return해준다.

 

vector<string> get_uv(string str) {
	int count_open = 0;
	int count_close = 0;
	int index = 1;

	if (str[0] == '(')
		count_open++;
	else
		count_close++;

	while (index < str.size() && count_open != count_close) {
		if (str[index] == '(')
			count_open++;
		else
			count_close++;
		index++;
	}

	string u = str.substr(0, index);
	string v = str.substr(index, str.size() - index);

	vector<string> ret;
	ret.push_back(u);
	ret.push_back(v);

	return ret;

}

 

- is_balanced()

 

 입력된 문자열이 균형잡힌 괄호 문자열인지 확인하는 함수이다. 자료구조 수업시간에서 가장 먼저 배운 stack을 활용한 괄호 문자열 판별을 사용하였다.

 

bool is_balenced(string str) {
	stack<char> s;
	for (auto it : str) {
		if (it == '(')
			s.push(it);
		else {
			if (s.empty() || s.top() != '(')
				return false;
			else
				s.pop();
		}
	}
	return s.empty();
}

 

- 전체 코드

 

 최대한 재귀 함수의 모양을 맞추고 싶어서 지문에 나오는 그대로를 구현해보았다. 솔직히 모양이 맞으니 눈에는 더 잘 보이는 것 같다. 다음은 전체 코드이다.

 

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

using namespace std;

vector<string> get_uv(string str) {
	int count_open = 0;
	int count_close = 0;
	int index = 1;

	if (str[0] == '(')
		count_open++;
	else
		count_close++;

	while (index < str.size() && count_open != count_close) {
		if (str[index] == '(')
			count_open++;
		else
			count_close++;
		index++;
	}

	string u = str.substr(0, index);
	string v = str.substr(index, str.size() - index);

	vector<string> ret;
	ret.push_back(u);
	ret.push_back(v);

	return ret;

}

bool is_balenced(string str) {
	stack<char> s;
	for (auto it : str) {
		if (it == '(')
			s.push(it);
		else {
			if (s.empty() || s.top() != '(')
				return false;
			else
				s.pop();
		}
	}
	return s.empty();
}

string bracket(string str) {
	if ((str == "") || is_balenced(str))
		return str;
	else {
		vector<string> uv = get_uv(str);
		string u = uv[0];
		string v = uv[1];

		if (is_balenced(u)) {
			return u + bracket(v);
		}
		else {
			string tmp = "(" + bracket(v) + ")";
			string new_u = u.substr(1, u.size() - 2);
			string final_u = "";

			for (auto it : new_u) {
				if (it == '(') {
					final_u += ")";
				}
				else {
					final_u += "(";
				}
			}
			return tmp + final_u;
		}
	}
}

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