C++ / 프로그래머스 / 괄호 변환

문제

 

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

프로그래머스

 

 

문제풀이

 

다른 방법으로 풀어야 하나 했는데 나온 그대로 코드를 작성하면 된다.

문제 잘 이해가 안 돼서 풀이를 참조했다.

 

입력이 빈 문제일 때까지 계속 재귀를 해야 한다.

코드를 더 세분화할 수 있긴 한데 크게 두 가지로 나누었다.

 

첫 번째는 isCorrect함수로 해당 문자열이 올바른 문자열인지를 판별하여 bool형을 return 하는 함수이다.

bool isCorrect(string s) {
    stack<char>stk;
    for (int idx = 0; idx < s.size(); ++idx) {
        if (s[idx] == '(') stk.push('(');
        else if (s[idx] == ')') {
            if (stk.empty()) return false;
            else if (stk.top() == '(') stk.pop();
        }
    }
    return true;
}

스택을 이용하여 스택에 top부분이 ')'라면 "()"형태의 올바른 괄호 문자열이 아니므로 false를 return 하면 된다.

반복문이 종료될 때까지 false를 return 하지 않는다면 true를 return 하면 된다.

 

string convert(string w) {
    if (w.empty()) return w;

변환을 하는 convert 함수이다.

문제에서 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다에 해당하는 부분이다.

 

    string ret(""), u(""), v("");
    int open(0), close(0), idx(0);

    for (idx = 0; idx < w.size(); ++idx) {
        if (w[idx] == '(') ++open;
        else if (w[idx] == ')') ++close;
        u += w[idx];
        if (open == close) {
            break;
        }
    }
    v = w.substr(idx + 1);

위 함수에 이어지는 부분이다.

반복문은 2번에 해당하는 부분이다 w를 u, v로 분리하는 과정이다.

u는 균형 잡힌 괄호 문자열로 더 이상 분리할 수 없어야 한다.

균형 잡힌 괄호 문자열은 '('와 ')'의 개수만 같으면 된다.

따라서 '('개수와 ')'개수가 같아지면 해당 부분까지 u가 되고 나머지 부분은 v가 된다.

 

    if (isCorrect(u) == true) ret = u + convert(v);
    else {
        ret = "(" + convert(v) + ")";

        for (int idx = 1; idx + 1 < u.size(); ++idx) {
            if (u[idx] == '(') ret += ")";
            else if (u[idx] == ')') ret += "(";
        }
    }
    return ret;

위 함수에 이어지는 부분으로 문제에서 3, 4번에 해당하는 부분이다.

isCorrect는 올바른 괄호 문자열인지 판단하는 함수이므로 true이면 올바른 괄호 문자열이므로 3번에 해당된다.

문자열 v에 대해 재귀로 convert함수를 실행한 결과를 u에 이어 붙이면 된다.

 

else문은 4번에 해당하는 부분이다.

u의 맨 앞과 끝자리를 제외한 부분을 반대 문자로 바꾸면 된다.

'('는 ')'로, ')'는 '('로 바꾸면 된다.

 

그다음 ret을 반환한다.

 

코드

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

bool isCorrect(string s) {
    stack<char>stk;
    for (int idx = 0; idx < s.size(); ++idx) {
        if (s[idx] == '(') stk.push('(');
        else if (s[idx] == ')') {
            if (stk.empty()) return false;
            else if (stk.top() == '(') stk.pop();
        }
    }
    return true;
}

string convert(string w) {
    if (w.empty()) return w;

    string ret(""), u(""), v("");
    int open(0), close(0), idx(0);

    for (idx = 0; idx < w.size(); ++idx) {
        if (w[idx] == '(') ++open;
        else if (w[idx] == ')') ++close;

        u += w[idx];
        if (open == close) {
            break;
        }
    }

    v = w.substr(idx + 1);

    if (isCorrect(u) == true) ret = u + convert(v);
    else {
        ret = "(" + convert(v) + ")";

        for (int idx = 1; idx + 1 < u.size(); ++idx) {
            if (u[idx] == '(') ret += ")";
            else if (u[idx] == ')') ret += "(";
        }
    }
    return ret;
}

string solution(string p) {
    return convert(p);
}