[2020 Kakao Blind] 괄호 변환 (C++)

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

코딩테스트 연습 - 괄호 변환 | 프로그래머스

 

별다른 알고리즘 없이 재귀와 문자열만 사용할 줄 알면 풀 수 있는 문제 입니다.

 

문제에서는 다음과 같은 것들을 요구하고 있습니다.

 

1. 올바른 괄호 문자열(빈 문자열 포함)인지 확인할 수 있는가?

 

2. 균형 잡힌 두 문자열을 구할 수 있는가?

 

3. 위의 2가지 과정을 재귀로 구현할 수 있는가?

 

이를 위해 저는 implement_string이라는 함수를 하나 만들었습니다.

 

이 함수는 문제에서 요구하는 것들을 만족시키면서 재귀적으로 작동합니다.

 

impelment_string 함수 안에서 문제에서 요구하는 것들을 순서대로 작성하기만 하면 문제를 풀 수 있습니다.

 

아래는 코드 입니다.

 

#include <string>
#include <vector>

using namespace std;

bool check_string(string str) {
	int cnt = 0;

	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') cnt += 1;
		else if (str[i] == ')') cnt -= 1;

		if (cnt < 0) return false;
	}

	if (cnt == 0) return true;
	else return false;
}

string implement_string(string str) {

	//올바른 문자열이거나 빈 문자열이면 그대로 반환
	if (check_string(str)) {
		return str;
	}
	
	//올바른 문자열이 아닐 경우 균형잡힌 문자열로 분리
	string u, v;
	int open_cnt = 0, close_cnt = 0;
	int i;

	for (i = 0; i < str.length(); i++) {
		if (str[i] == '(') open_cnt += 1;
		else if (str[i] == ')') close_cnt += 1;

		if (open_cnt == close_cnt) {
			break;
		}
	}

	for (int j = 0; j <= i; j++) u += str[j];
	for (int j = i + 1; j < str.length(); j++) v += str[j];

	if (check_string(u)) {
		return u + implement_string(v);
	}

	else {
		string empty_str;
		
		empty_str += "(";
		empty_str += implement_string(v);
		empty_str += ")";

		for (int j = 0; j < u.length(); j++) {
			if (j == 0 || j == u.length() - 1) continue;
			if (u[j] == '(') empty_str += ")";
			else if (u[j] == ')') empty_str += "(";
		}
		return empty_str;
	}
}

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