2020 카카오 코딩테스트 - 괄호 변환

문제 설명

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

간단히 설명하자면 괄호 '('와 ')'를 올바르게 배치하는 문제입니다.

풀이 핵심 keyword

재귀함수, 스택(stack)

문제풀이

문제 설명에 답이 대부분 있습니다.

첫번째 단계

는 주어진 p를 u,v로 나누는것 입니다.

u는 더이상 나눠지지 않는 괄호의 첫 문자열, v는 나머지 입니다.

예를들어 "(())()()"와 같은 문자열이 주어졌다면 u는 "(())" v는 "()()"가 됩니다.

처음 문자열로 "(" 또는 ")"가 올수있기때문에 아무거나 기준점을 잡고 아래와 같이 계산했습니다.

• "("를 기준으로 "("가 나오면 +1, ")"가 나오면 -1로 계산하여 첫 0이 되는 시점이 더이상 나눌 수 없는 괄호로 판단
• + 수치가 되었다가 0이 되는 순간
• (로 시작해서 )로 끝나는 경우입니다.
  i.e. "(())()()"
• - 수치가 되었다가 0이 되는 순간
• )로 시작해서 (로 끝나는 경우입니다.
  i.e.  "))))((((()()"

static void _divide_uv(string p, string &u, string &v)
{
	//divide u,v
	int left = 0;
	int copylen = 0;
	for(int i=0;i<p.size();i++) {
		if(p[i] == '(') {
			left++;
		} else {
			left--;
		}
		if(left==0) {
			copylen = i+1;
			cout << "count " << copylen << endl;
			break;
		}
	}

	u = p.substr(0,copylen);
	v = p.substr(copylen, p.size()-copylen);
}

두번째 단계

는 나눠진 u가 올바른지 판단하는 것 입니다.

판단하는 방법은 stack에 괄호를 넣으면서 짝이 맞으면 stack을 지우는 방법입니다.

만약에 마지막까지 검사를 다 했는데 stack이 비어있다면 u는 올바른 괄호입니다.

static bool _check_vaild(string u)
{
	vector<char> uStack;
	
	for(int i=0; i<u.size(); i++) {
		if(u[i] == '(') {
			uStack.push_back(u[i]);
		} else if(u[i] == ')') {
			if(uStack.empty()) {
				uStack.push_back(u[i]);
				//false
				break;
			} else if(uStack.back() == '(') {
				uStack.pop_back();
			}
		}
	}

	if(uStack.empty()) {
		return true;
	} else {
		return false;
	}
}

세번째 단계

는 올바른 괄호와 올바르지 않은 괄호의 처리입니다.

이 부분은 문제 안에 답이 그대로 있기때문에 따로 설명은 하지 않겠습니다.

string solution(string p) {
	string ret;

	if(p.empty()) {
		return "";
	}

	//divide u,v
	string u,v;
	_divide_uv(p,u,v);
	//cout << "divide u :" << u << "v :" << v << endl;

	//check vaild u
	bool uValid = _check_vaild(u);

	if(uValid) {
		//if invaild, try to divide u,v again through v.
		cout << "u is vaild, check vaild v again" << endl;
		string v2 = solution(v);
		ret = u+v2;
		
	} else {
		//if vaild, try to change bracket to right way.
		cout << "u is invaild before : " << u << endl;

		string u2 = "(";
		string v2 = solution(v);
		u2+=v2;
		u2 += ")";

		u.erase(0,1);
		u.erase(u.size()-1,1);

		for(int i=0; i<u.size(); i++) {
			if(u[i] == '(') {
				u[i] = ')';
			} else {
				u[i] = '(';
			}
		}
		u = u2 + u;

		ret = u;

	}

	return ret;
}