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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

문제가 길어서 어렵다고 겁먹을 수 있지만 명시된 규칙대로 구현하면 의외로 쉽게 해결할 수 있다. '균형잡힌 괄호 문자열'의 여부는 stack을 이용하여 확인하였다.
자세한 풀이는 주석으로 남겨두었다.

코드

C++

#include <string>
#include <vector>
#include <stack>

using namespace std;

// 올바른 괄호 문자열인지 체크해주는 함수
bool isCorrect(string str) {
    stack<char> s;
    for (char c : str) {
        if (c == '(') s.push(c);
        else {
            if (s.empty()) return false;
            s.pop();
        }
    }
    if (!s.empty()) return false;
    return true;
}

// 문자열 u, v로 분리해주는 함수
pair<string, string> cutUV(string str) {
    // 괄호의 개수를 체크하는 변수 '(' 이면 ++, ')' 이면 --
    int cnt = 0;
    int idx = 0;
    for (char c : str) {
        idx++;
        if (c == '(') cnt++;
        else cnt--;
        // 괄호의 개수가 제일 처음 같아지는 경우 u, v를 분리한다
        if (cnt == 0) break;
    }
    return { str.substr(0, idx), str.substr(idx, str.length() - idx) };
}

// 규칙 함수
string solution(string p) {
    string answer = p;
    // 올바른 괄호 문자열인 경우
    if (isCorrect(answer)) return answer;
    pair<string, string> s = cutUV(answer);
    string u = s.first;
    string v = s.second;
    // u가 올바른 괄호 문자열인 경우
    if (isCorrect(u)) answer = u + solution(v);
    else {
        answer = "(" + solution(v) + ")";
        // u의 앞, 뒤 괄호를 제거
        u = u.substr(1, u.length() - 2);
        // u의 괄호를 뒤집는 부분
        for (int i = 0; i < u.length(); i++) {
            char c = u[i];
            if (c == '(') u[i] = ')';
            else u[i] = '(';
        }
        answer += u;
    }
    return answer;
}

Python3

def solution(p):
    if is_correct(p):
        return p

    u, v = divide_string(p)

    if is_correct(u):
        return u + solution(v)
    else:
        temp = '(' + solution(v) + ')'
        u = list(u[1:-1])
        for i in range(len(u)):
            if u[i] == '(':
                u[i] = ')'
            else:
                u[i] = '('
        return temp + "".join(u)


def is_correct(p):
    stack = []
    for i in p:
        if i == '(':
            stack.append(i)
        else:
            if len(stack) == 0:
                return False
            stack.pop()
    if len(stack) == 0:
        return True
    return False


def divide_string(p):
    idx = 0
    count = 0
    for i in range(len(p)):
        idx += 1
        if p[i] == '(':
            count += 1
        else:
            count -= 1
        if count == 0:
            break
    u = p[:idx]
    v = p[idx:]
    return (u, v)