[2020 카카오 공채] 괄호 변환

분류 

시뮬레이션

요구사항

균형잡힌 괄호열을 올바른 괄호열로 변환 시켜 준다

풀이

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

-> 시작 혹은 dfs 진입시 빈 문자열일 경우 빈 문자열 반환

 

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

-> 최초의 균형잡힌 문자열 u와 나머지 v로 나누기

 

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

-> u를 check()하고 v를 재귀 함수로 실행

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

-> v의 결과를 u에 붙인 후 반환

 

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

-> u를 check()하고 아니라면 아래 과정 수행

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

-> 그대로 실행

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

-> v에 대해서 dfs 실행 후, '('에 붙인다

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

-> 그대로 실행

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

-> 전체를 뒤집는게 아니라 현재 괄호 방향에 대해서 괄호방향을 바꿔서 뒤에 붙인다

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

-> 반환

 

문제 그대로 재귀함수를 사용하여 구현

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#include <deque>
#include <map>
#include <string>
#include <vector>
#include <stack>
using namespace std;
//현재 문자열이 올바른 문자열인지 확인하는 함수
bool check(string s){
	if(s.size()==0){
		return true;
	}
	stack<char> st;
	//'(' 일경우 스택에 넣고, 아닐 경우 pop하거나 리턴
	for(int i=0 ; i <s.size() ; i++){
		if(s[i] =='('){
			st.push(s[i]);
		}
		else{
			if(st.empty()){	//예외 처리
				return false;
			}
			else 
				st.pop();
		}
	}
	//올바른 문자열인지 확인
	if(st.empty())
		return true;
	else 
		return false;
}
string dfs(string s){
	//빈 문자열일 경우 반환
	if(s.size()==0) return s;
	//u, v로 분리하기 최초로 나누어지는 문자열
	int open_cnt=0;
	int close_cnt=0;
	int u_len=0;
	string temp="";
	//u의 길이 찾기
	for(int i=0 ; i <s.size() ; i++){
		if(s[i]=='(')
			open_cnt++;
		else
			close_cnt++;
		if(open_cnt !=0 && close_cnt!=0){
			if(open_cnt==close_cnt)
				break;
		}
	}
	u_len=open_cnt+close_cnt;
	//u와 v 나눈 것으로 행동하기
	string u = s.substr(0,u_len);
	string v = s.substr(u_len,-1);
	//맞을 경우
	if(check(u)){
		return u+dfs(v);
	}
	//아닐 경우
	else{
		temp +='(';
		temp+=dfs(v);
		temp+=')';
		auto pos =u.begin();
		u.erase(pos);
		for(int i=0 ; i <u.size()-1; i++) pos++;
		u.erase(pos);
		string nowtemp;
		for(auto i: u){
			if(i=='('){
				nowtemp+=')';
			}
			else{
				nowtemp+='(';
			}
		}
		temp+=nowtemp;
	}
	return temp;
}

string solution(string p) {
    string answer = "";
	if(p.size()==0){
		return answer=p;
	}
	if(check(p))
		answer=p;
	else
		answer = dfs(p);
	return answer;

}