문제 출처

1. 문제설명

  • 닫는 괄호, 여는 괄호의 개수가 같으면 균형잡힌 괄호 문자열
  • 괄호의 짝까지 모두 맞는 경우 올바른 괄호 문자열
  • 균형잡힌 괄호 문자열을 올바른 괄호 문자열로 변환하는 문제

  • 규칙

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


2. 입/출력

  • 문자열 p
    • p는 ‘(‘ 와 ‘)’ 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수
    • 문자열 p를 이루는 ‘(‘ 와 ‘)’ 의 개수는 항상 같다.
  • 올바른 괄호 문자열을 리턴


3. 문제 분류

  • Simulation


4. 알고리즘 설계

  • 문제에 언급된 프로세스를 그대로 따르면 되기 때문에 주석을 포함한 코드를 첨부하겠다.


5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

// 문자열이 올바른 문자열인가?
// 스택을 이용해서 열고 닫히는 순서가 올바른지 체크
// for문 종료 후 스택이 비어있지 않다면 올바르지 않은 문자열
bool is_right(string s) {
    stack<char> st;
    
    for(char c : s) {
        if(c == '(') st.push('(');
        else {
            if(st.empty()) return false;
            else st.pop();
        }
    }
    return st.empty();
} 

string solution(string p) {
    string ans = "";
    
    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
    if(p == "") return p;
    
    // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    string u, v;
    int l = 0, r = 0;
    for(int i=0; i<p.size(); i++) {
        char c = p[i];
        
        if(c == '(') l++;
        else if(c == ')') r++;
        
        if(l == r) {
            u = p.substr(0, i+1);
            v = p.substr(i+1);
            break;
        }
    }
    
    // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
    if(is_right(u)) {
        v = solution(v);
        ans = u + v;  // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
    }
    
    // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
    else {
        // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
        ans = "(";
        // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
        ans += solution(v);
        // 4-3. ')'를 다시 붙입니다.
        ans += ")"; 
        
        // 4-4. u의 첫 번째와 마지막 문자를 제거하고,
        u.erase(0, 1);
        u.erase(u.size()-1, 1);
        
        // 4-4. 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        for(char c : u) {
            if(c == '(') ans += ')';
            else ans += '(';
        }
    }
    
    return ans;
}


4. 소감

  • 문제를 제대로 파악한다면, 매우 쉬운 편에 속하는 문제였다.