[프로그래머스 60058] - 카카오 기출 괄호 변환

문제출처

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

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

 

문제풀이

문제에서 주어진대로 구현해주면 된다. 올바른 괄호를 체크할때 스택을 사용했다. 딱히 어려운 부분은 없고 문제를 정확히 읽고 구현해주면 되는 문제인데 u를 구할때 약간 생각이 필요했다. 문자열을 탐색하면서 '('의 개수와 ')'의 개수가 같아질 때가 u이고 나머지 문자열이 v가 된다.

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EA%B4%84%ED%98%B8%20%EB%B3%80%ED%99%98.cpp

sw93/algorithm

 

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

// 올바른 괄호 문자열 체크
bool isCorrectBracket(string bracket) {
    stack<char> st;
    for (int i=0; i<bracket.size(); i++) {
        if (bracket[i] == '(') {
            st.push(bracket[i]);
        } else if (bracket[i] == ')') {
            if (st.empty()) {
                return false;
            } else {
                st.pop();
            }
        }
    }
    
    if (st.empty()) return true;
    else return false;
}

// 재귀
string go(string p) {
    // 1번
    if (p == "") {
        return p;
    }
    
    // 2번
    string u = "", v = "";
    int left = 0, right = 0;
    for (int i=0; i<p.size(); i++) {
        if (p[i] == '(') left++;
        else if (p[i] == ')') right++;
        if (left == right) {
            u = p.substr(0, i + 1);
            v = p.substr(i + 1);
            break;
        }
    }
    
    // 3번
    if (isCorrectBracket(u)) {
        return u + go(v);
    } else {    // 4번
        string ret = "(" + go(v) + ")";
        u = u.substr(1, u.size() - 2);
        for (int i=0; i<u.size(); i++) {
            if (u[i] == '(') u[i] = ')';
            else if (u[i] == ')') u[i] = '(';
        }
        return ret + u;
    }
}

string solution(string p) {
    string answer = "";
    if (isCorrectBracket(p)) return p;
    answer = go(p);
    return answer;
}