[프로그래머스 2020 KAKAO BLIND RECRUITMENT] 괄호 변환

문제

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

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

 

문제 풀이

 1. 균형잡힌 문자열인지는 s를 탐색하며 '(' , ')'의 개수를 비교하면된다.

 2. 올바른 괄호 문자열인지는 해당 문자가 '('이면 스택에 넣고, ')'일 때 스택에서 pop한다고 할 때 스택이 비어있는데pop하는 경우를 확인하면 된다.    

 

코드

#include <string>
#include <vector>

using namespace std;

string f(string w) {
	vector<char> st;
	int sz = w.length(), o = 0, c = 0, idx= -1;
	bool no = 0;
	if (w.empty()) return "";
	for (int i = 0; i < sz; i++) {
		if (w[i] == '(') st.push_back('('), o++;
		else {
			c++;
			if (st.empty()) no = 1;
			else st.pop_back();
		}
		if (o == c) {
			idx = i;
			break;
		}
	}
	string u = w.substr(0, idx + 1), v = w.substr(idx + 1);
	if (!no) return u + f(v);
	else {
		string tmp = "(" + f(v) + ')';
		for (int i = 1; i < u.size() - 1; i++)
			if (u[i] == '(') tmp += ')';
			else tmp += '(';
		return tmp;
	}
}

string solution(string p) {
	string answer = f(p);
	return answer;
}