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

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

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

---

 

-풀이-

먼저, 문자열이 올바른 괄호 문자열인지 확인하는 rightString함수를 만든다.

이는 stack을 이용하여, 문자열을 탐색하며 열린괄호를 만나면 push를 해준다.

반대로 닫힌 괄호를 만났을때 두가지 경우가 있다.

 

1. 스택이 비어있거나, 스택의 top부분이 닫힌 괄호일떄

이경우는 앞에 열린괄호 짝이 없는데, 닫힌괄호가 나온 경우가 되므로 이 경우는 올바른 괄호 문자열이 아니다 라고 할 수 있으므로, false를 return 해준다.

 

2. 스택의 top부분이 열린 괄호일때

이때는, 지금 만난 닫힌괄호의 짝이므로, 열린괄호를 pop해준다.

 

이 두가지경우를 고려해서 문자열끝까지 탐색을 했을때, 스택이 비어있다면, 모든 괄호가 짝을 만났다는 것이므로, 올바른 괄호 문자열이라고 할 수 있으므로, true를 return 해준다.

 

만약 스택이 비어있지 않다면, 열린괄호가 짝을 찾지 못했다는 뜻이므로, false를 return해준다.

bool rightString(string str){
    stack<char> st;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){
            st.push(str[i]);
        }
        else{
            if(st.empty()||st.top()!='('){
                return false;
            }
            else{
                st.pop();
            }
        }
    }
    if(st.empty()){
        return true;
    }
    else{
        return false;
    }
}

 

처음에 이 함수를 이용하여 올바른 괄호 문자열인지 판별 후, 맞으면 answer에 그 문자열을, 아니면, 올바른 괄호 문자열을 만드는 함수를 이용하여 문자열을 구해준다.

 

올바른 괄호 문자열을 구하는 함수는 다음과 같다.

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. 생성된 문자   열  을 반환합니다.

 

먼저 받은 w를 균형잡힌 괄호 문자열 u와 v로 분리해야한다. 하지만 2번 조건에 의해 더이상 분리할 수 없는 균형잡힌 괄호 문자열로 분리해야한다.

이는 문자열을 탐색하며, 열린괄호와 닫힌괄호의 개수가 0이아닌 자연수로 같아질때까지 뽑아낸다면, u를 만들 수 있게된다. 그런뒤 나머지 문자열을 뽑아 v를 만들어주면된다.

int n1=0,n2=0;
string s1="";
string s2="";
for(int i=0;i<str.size();i++){
  if((n1||n2)&&(n1==n2)){
  	s2+=str[i];
  }
  else{
    if(str[i]=='(') n1++;
    if(str[i]==')') n2++;
    s1+=str[i];
  }
}

 

이렇게 만든뒤, u를 올바른 괄호 문자열판별 함수를 통해 참인지 거짓인지에 따라 요구하는대로 return 해주면된다.

1) u가 올바른 괄호 문자열일때.

v문자열을 다시 올바른 괄호 문자열을 만들어주는 함수를 호출하여 재귀적으로 호출한뒤, 만들어진 문자열을 u와 합쳐서 return한다.

 

2) 아닐때

위에 4번과정을 실행해준다.

 

이때, 재귀함수의 베이스 케이스는, 빈 문자열이 들어왔을때 빈 문자열을 리턴해주는것을 잊지 말아야한다.

if(rightString(s1)){
	return s1+make_right(s2);
}
else{
  string ret="("+make_right(s2)+")";
  for(int i=1;i<s1.size()-1;i++){
  	if(s1[i]=='('){
      ret+=")";
    }
    else{
    	ret+="(";
    }
  }
  return ret;
}

 

-코드-

#include <string>
#include <vector>
#include<stack>
using namespace std;

bool rightString(string str){
    stack<char> st;
    for(int i=0;i<str.size();i++){
        if(str[i]=='('){
            st.push(str[i]);
        }
        else{
            if(st.empty()||st.top()!='('){
                return false;
            }
            else{
                st.pop();
            }
        }
    }
    if(st.empty()){
        return true;
    }
    else{
        return false;
    }
}

string make_right(string str){
    if(str=="") return "";
    int n1=0,n2=0;
    string s1="";
    string s2="";
    for(int i=0;i<str.size();i++){
        if((n1||n2)&&(n1==n2)){
            s2+=str[i];
        }
        else{
            if(str[i]=='(') n1++;
            if(str[i]==')') n2++;
            s1+=str[i];
        }
    }
    if(rightString(s1)){
        return s1+make_right(s2);
    }
    else{
        string ret="("+make_right(s2)+")";
        for(int i=1;i<s1.size()-1;i++){
            if(s1[i]=='('){
                ret+=")";
            }
            else{
                ret+="(";
            }
        }
        return ret;
    }
}

string solution(string p) {
    string answer = "";
    if(rightString(p)){
        answer=p;
    }
    else{
        answer=make_right(p);
    }
    return answer;
}