2020 카카오 공채: 괄호 변환

[문제 링크]

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

---

스택의 대표적인 문제라고 볼 수 있는 괄호 체크와 분할정복이 섞인 문제였던거 같다.

 

입력으로 주어지는 문자열 p는 곧 문자열 u = p와 빈 문자열 v가 주어진 형태라고 볼 수 있다.

따라서 문제에서 요구하는 알고리즘대로 구현하면 된다.

 

먼저 문자열 p가 올바른 괄호 문자열인지 확인해야 한다.

만약 올바른 괄호 문자열이라면 그대로 출력해주면 되고, 올바른 괄호 문자열이 아닐 경우 p를 u와 v로 나눠야 하는데

문제에서 u는 더이상 쪼개질 수 없는 균형잡힌 문자열로 나눠야 한다고 나와있기 때문에 '(' 와 ')' 의 개수가 같아지는 지점을 기준으로 u와 v로 나누면 된다.

 

마지막으로 나눠진 u에 대해서 올바른 괄호 문자열인지 확인하고, 문제에서 시키는데로 문자열을 완성해주면 된다.

---

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

bool match(const string& p)
{
	stack<char> temp;

	for (int i = 0; i < p.length(); i++)
	{
		if (p[i] == ')')
		{
			if (temp.empty())
				return false;
			
			temp.pop();
		}
		else
			temp.push(p[i]);
	}
	if (!temp.empty())
		return false;

	return true;
}

string solution(string p) {
	string answer = "";
	
	bool check = match(p);

	if (check)
		return p;
	else
	{
		int uLen;
		stack<char> temp;

		for (uLen = 0; uLen < p.length(); uLen++)
		{
			if (!temp.empty() && temp.top() != p[uLen])
				temp.pop();
			else
				temp.push(p[uLen]);

			if (temp.empty())
				break;
		}
		uLen++;

		string u = p.substr(0, uLen);
		string v = p.substr(uLen);

		check = match(u);

		if (check)
			answer = u + solution(v);
		else
		{
			answer = '(' + solution(v) + ')';
			for (int i = 1; i < uLen - 1; i++)
			{
				if (u[i] == '(')
					answer.push_back(')');
				else
					answer.push_back('(');
			}
		}
	}

	return answer;
}

알고리즘 200일 프로젝트 - 138 day