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

프로그래머스 괄호 변환 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60058

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

문제 풀이

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

• 이 문제는 문자열 처리 문제로 위의 과정을 구현해 주시면 됩니다.
• "올바른 괄호 문자열" 검증 과정은 다음과 같습니다.
  • "올바른 괄호 문자열" 검증을 위해 stack을 하나 선언합니다. 
  • 문자열을 처음부터 끝까지 반복하면서 ' ( ' 라면 stack에 push
  • ' ) ' 라면 pop 합니다. 이 때 pop 하기 전에 stack이 비어있는지 확인해야 합니다. stack이 비어있다면 괄호의 짝이 맞지 않는 것이기 때문에 false를 리턴합니다. -> ' ) ' 가 더 많은 경우
  • 마지막으로 empty()를 리턴합니다. stack의 요소가 모두 제거되지 않고 남아있다는 것은 괄호의 짝이 맞지 않는다는 것이기 때문에 empty 일 경우 true, 아닐 경우 false가 리턴됩니다. -> ' ( ' 가 더 많은 경우

코드

#include <string>
#include <stack>

using namespace std;

// "올바른 괄호 문자열" 검증
bool check(string p) {
    stack<char> st;
    
    for(auto c: p) {
        if(c == '(') st.push(c);
        else {
            if(st.empty()) return false;
            st.pop();
        }
    }
    
    return st.empty();    
}

string solution(string p) {
    if(p.empty()) return p; // step 1
    string answer = "";
    
    string u = "", v = "";
    int l = 0, r = 0;
    
    // step 2
    for(int i=0; i<p.length(); ++i) {
        if(p[i] == '(') l++;
        else r++;
        
        if(l == r) {
            u = p.substr(0, i+1);
            v = p.substr(i+1);
            break;
        }
    }
    
    if(check(u)) answer = u + solution(v); // step 3
    else { // step 4
        answer = "(" + solution(v) + ")"; // step 4-1,2,3
        
        // step 4-4
        for(int i=1; i<u.length()-1; ++i) {
            answer += u[i] == '(' ? ')' : '(';
        }
    }
    
    return answer;
}

실행 결과