[ 2020 KAKAO BLIND RECRUITMENT ] 괄호 변환

 

 

 

  CatServant  

 문제 설명

 

문제를 잘못 이해해서 한참 헤맨 문제였다.

 

입력 조건은 아래와 같다.

1.  '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수
2. 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같다.

'균형 잡힌 문자열'을 아래와 같은 조건으로 통해 '올바른 괄호 문자열'로 변환할 수 있다. 이 조건을 제대로 안 읽어서 한참을 고민했다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

 

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

 

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

   4-3. ')'를 다시 붙입니다.

   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

   4-5. 생성된 문자열을 반환합니다.

 

잘못 생각했던 예시를 들자면 

① "()))(("

이와 같은 경우, 

1.1) u = "()" , v = "))(("  → u는 올바른 괄호 문자열이므로 res = "()" + Solve("))((")

1.2) u = "))((", v = ""  → v는 올바른 괄호 문자열이 아니므로 res = "(" + Solve("") + ")" + "()" 와 같은 순서로 진행된다.

결과적으로 "()()()"가 답이 된다.

 

② ")()()("

1.1) u = ")(", v = ")()(" → u는 올바른 괄호 문자열이 아니므로 res = "(" + Solve(")()(") + ")" + ""

1.2) u = ")(", v = ")(" → u는 올바른 괄호 문자열이 아니므로 res = "(" + Solve(")(") + ")" + ""

1.3) u = ")(", v = "" → u는 올바른 괄호 문자열이 아니므로 res = "(" + Solve("") + ")"와 같은 순서로 진행된다.

결과적으로 "((()))"가 답이 된다.

 

 

 Code - C/C++

#include <iostream>
#include <stack>

using namespace std;

bool isCollected(string str) {
	stack<char> st;

	for (int i = 0; i < str.size(); i++) {
		if (str[i] == '(')
			st.push('(');
		else if (!st.empty() && str[i] == ')')
			st.pop();
		else
			return false;
	}
	return st.empty();
}

string Solve(string str) {
	if (str.empty()) return str;

	int open, close;
	string left, right;
	string temp;

	// 나누기
	open = close = 0;
	int idx = 0;
	for ( idx = 0; idx < str.size(); idx++) {
		if (str[idx] == '(') open++;
		else close++;

		if (open == close) break;
	}
	left = str.substr(0, idx + 1);
	right = str.substr(idx + 1, str.size());
	
	if (isCollected(left)) {
		// 올바른 괄호 문자열인 경우
		temp.append(left);
		temp.append(Solve(right));
	}
	else {
		// 올바른 괄호 문자열이 아닌 경우
		temp.push_back('(');
		temp.append(Solve(right));
		temp.push_back(')');

		string leftTemp = left.substr(1, left.size() - 2);
		left.clear();
		for (int i = 0; i < leftTemp.size(); i++) {
			if (leftTemp[i] == '(')
				left.push_back(')');
			else
				left.push_back('(');
		}
		temp.append(left);
	}

	return temp;
}

string solution(string p) {
	if (isCollected(p)) return p;
    
	string res = Solve(p);
	return res;
}

 

 

출처

1. https://programmers.co.kr/learn/challenges

프로그래머스