2020 Kakao blind 60058 - 괄호 변환(스택, 재귀 구현) c++

 

- 문제에서 지시하는 데로 구현해야 올바른 괄호 문자열이 만들어지는데, 재귀를 이용해야한다. 
- 괄호가 올바른지, 균형잡혔는지 카운트하기 위해서 스택을 이용하거나 혹은 직접 int변수로 카운트 할 수 있다. 

- 처음 시작 시에 균형잡힌 문자열이 주어지는 것을 이용해서 p를 2개의 균형잡힌 문자열 u,v로 나눈 뒤에 그 중 u를 옳바른 문자열로 만들어 주고, 남은 v를 재귀적으로 다시 같은 로직을 이용하여 결과적으로 옳바른 문자열 + 옳바른 문자열 + 옳 +옳... 을 리턴하도록 만들어주는 것이 포인트이다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool isCorrect(string& s) {
    int open = 0;
    for (char& ch : s) {
        if (ch == '(')
            ++open;
        else
            --open;
        if (open < 0) return false;
    }

    if (open == 0) return true;
    return false;
}

string solution(string p) {  // p는 균형잡힌 괄호 문자열
    if (p == "") return "";

    int pos, open = 0;
    for (int i = 0; i < p.length(); ++i) {
        if (p[i] == '(')
            ++open;
        else
            --open;
        if (open == 0) {
            pos = i + 1;
            break;
        }
    }

    string u = p.substr(0, pos);
    string v = p.substr(pos);

    if (isCorrect(u)) return u + solution(v);

    for (char& ch : u) {
        if (ch == '(')
            ch = ')';
        else
            ch = '(';
    }

    return '(' + solution(v) + ')' + u.substr(1, u.size() - 2);
}

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

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