[프로그래머스][C++] 괄호 변환

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

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

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

 

#include <string>
#include <vector>

using namespace std;


string solution(string p) {
	string answer = "";
	string u;
	string v;
	string tmp;
	int front = 0;
	int back = 0;
	int count = 0;
	int max = p.length() / 2;
	int i = 0;
	bool check= true;

	if (p.length() == 0) {
		return "";
	}

	// 1. 균형잡힌 괄호 문자열 확인
	while (1) {
		count++;
		if (p[count-1] ==  ')' ) {
			front++;
		}
		else if (p[count - 1] == '(') {
			back++;
		}

		if (front == max && back == max) {
			break;
		}
		if (front !=0 && back != 0 && front == back) {
			break;
		}
	}

	// 2. 배열 나누기
	u = p.substr(0, count);
	if (count != p.length()) {
		v = p.substr(count, p.length());
	}
	else {
		v = "";
	}

	// 3. u가 올바른 괄호 문자열인지 확인 (u는 무조건 균형잡힌 괄호 문자열임)
	front = 0;
	back = 0;
	check = true;
	for (i = 0; i < count; i++) {
		if (u[i] == '(' ) {
			front++;
		}
		else if (u[i] == ')') {
			back++;
		}

		front -= back;
		if (back != 0)
			back--;

		if (front < 0) {
			check = false;
			break;
		}
	}
	// 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
	if (check == true) {
		answer += u;
		answer += solution(v);
		return answer;
	}
	// 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
	else {
		// 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
		answer += "(";
		// 4 - 2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
		answer += solution(v);
		// 4 - 3. ')'를 다시 붙입니다.
		answer += ")";
		// 4 - 4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
		for (i = 1; i < u.length() - 1; i++) {
			if (u[i] == '(') {
				tmp += ")";
			}
			else if (u[i] == ')') {
				tmp += "(";
			}
		}
		answer += tmp;
		return answer;		
	}

}

 

꾸준히 하다보면 실력이 늘겠지..