[카카오 코딩 테스트] 괄호 변환

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

2번 괄호 변환 문제입니다.

 

문제 그대로 따라하기만 하면 되는 문제이지만, 생각보다 정답률은 낮은 문제네요.

 

재귀에 대해 이해만 하고 있다면 문제에서 말하는 순서대로 따라만 하면 쉽게 풀리는 문제였습니다.

 

아래는 해당 코드이고 각 단계별로 주석 달아두었습니다.

#include <iostream>
#include <string>
#include <vector>
#include <stack>
 
using namespace std;
 
bool isCorrect(string p) {
    stack<char> s;
    for (int i = 0; i < p.length(); i++) {
        if (p[i] == '(')
            s.push('(');
        else {
            if (s.empty())
                return false;
            else
                s.pop();
        }
    }
    return s.empty();
}
 
string divide(string p) {
    // 1번
    if (p.length() == 0) return "";
 
    // 2번
    string u, v;
    int left = 0, right = 0;
    for (int i = 0; i < p.length(); i++) {
        if (p[i] == '(') left++;
        else right++;
        if (left == right)
            break;
    }
    u = p.substr(0, left + right);
    v = p.substr(left + right, p.length());
    // 3번
    if (isCorrect(u)) {
        // 3-1번
        return u += divide(v);
    }
    // 4번
    else {
        // 4-1번
        string tmp = "(";
        // 4-2번
        tmp += divide(v);
        // 4-3번
        tmp += ")";
        // 4-4번
        u = u.substr(1, u.length() - 2);
        for (int i = 0; i < u.length(); i++) {
            if (u[i] == '(') tmp += ")";
            else tmp += "(";
        }
        // 4-5번
        return tmp;
    }
}
 
string solution(string p) {
    string answer = divide(p);
    return answer;
}
int main() {
    string p = "()))((()";
    cout << solution(p);
    return 0;
}

 

질문이나 지적사항은 댓글 부탁드립니다 :)