[Programmers] 괄호 변환 - travelbeeee

문제 : 2020 카카오 BLINE RECRUITMENT '괄호변환'

---

구현 문자열 스택

문제에서 정확하게 알고리즘을 명시해줘서 구현만 하면 되는 문제입니다.

1) 입력으로 들어온 문자열이 빈 문자열인지 아닌지 체크, 빈 문자열이라면 빈 문자열을 return 해줍니다.

2) 입력으로 들어온 문자열을 순회하며, '(' 와 ')' 의 개수를 count하고 빈 문자열 u에 concat을 해줍니다. 이때, '(' 와 ')' 의 개수가 같아지면 u가 균형잡힌 괄호 문자열이므로 break 해주고, 나머지 부분은 v 에 concat을 해줍니다.

3) u가 올바른 괄호 문자열인지 자료구조 stack 을 이용해 check합니다.

 3-1) u가 올바른 괄호 문자열이라면 u + solution(v) 를 return 해주면 됩니다.

 3-2) u가 올바른 괄호 문자열이 아니라면, '(' + solution(v) + ')' 와 u의 첫 번째와 마지막 문자를 제거한 나머지 부분들 뒤집어서 return 해주면 됩니다.

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

string solution(string p) {
	string answer = "";
	string u = "", v = "";

	if (p == "")
		return answer;
	
	// u 랑 v로 나눔.
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < p.length(); i++) {
		if (p[i] == '(')
			cnt1++;
		else
			cnt2++;

		u += p[i];
		if (cnt1 != 0 && cnt1 == cnt2)
			break;
	}

	for (int i = u.length(); i < p.length(); i++)
		v += p[i];
	
	// u 가 올바른 괄호 문자열인지 체크하자.
	bool check = false;
	stack<char> s;
	for (int i = 0; i < u.length(); i++) {
		if (u[i] == '(')
			s.push(u[i]);
		else {
			if (s.empty()) {
				check = true;
				break;
			}
			s.pop();
		}
	}
	if (!s.empty())
		check = true;
	if (!check) { // u가 올바른 괄호 문자열
		answer = answer + u + solution(v);
	}
	else {
		string temp = "";
		for (int i = 1; i < u.length() - 1; i++)
			if (u[i] == '(')
				temp += ')';
			else
				temp += '(';
		answer = answer + '(' + solution(v) + ')' + temp;
	}
	return answer;
}

---