[프로그래머스][2020 KAKAO BLIND][C++] 괄호 변환

문제

프로그래머스 2020 KAKAO BLIND RECRUITMENT - 괄호 변환 (Level 2)

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

 

---

문제 풀이

접근 방식

이 문제는 문자열을 주어진 알고리즘을 수행하여 올바른 괄호 문자열로 변환하는 문제로,

2020 카카오 블라인드 채용 1차 코딩테스트 2번 문제이다.

 

이 문제는 아래의 사진과 같이 주어진 알고리즘을 그대로 구현하면 되는 문제였다.

재귀적으로 구현해야해서 이해가 쉽지는 않았으나, 주어진대로만 수행하면 문제를 해결할 수 있었다.

 

올바른 괄호 문자열로 변환하는 알고리즘

 

우선 바꿔야할 문자열과 길이를 매개변수로 받아서 올바른 문자열을 리턴해주는 correct 함수를 만들어주었다.

이 함수에서는 문자열을 u와 v로 분리하는 작업을 수행하였고,

u가 올바른 괄호 문자열인 경우에는 u에 correct 함수에 v를 넣어 재귀적으로 수행한 값을 합쳐 답을 도출하였고,

균형잡힌 괄호 문자열인 경우에는 '('와 ')' 사이에 correct(v, v의 길이)의 값을 합쳐주고,

change 함수에 u를 넣어서 u의 양쪽 괄호를 제거하고,

남은 모든 괄호를 반대 방향으로 바꿔준 값을 합쳐서 답을 도출하였다.

 

---

풀이 코드 - C++

#include <string>

using namespace std;

string change(string s, int len) {
    string temp = "";
    for(int i = 1; i < len - 1; i++){
        if(s[i] == '(') temp += ')';
        else temp += '(';
    }
    return temp;
}

string correct(string s, int len) {
    if(len == 0) return "";
    int cnt = 0;
    string u, v;
    string result = "";
    bool check = true;
    for(int i = 0; i < len; i++) {
        if(s[i] == '(') cnt++;
        else cnt--;
        if(cnt < 0)
            check = false;
        if(cnt == 0){
            u = s.substr(0, i + 1);
            v = s.substr(i+1, len - i - 1);
            if(check){  // 올바른 괄호 문자열
                result += u;
                result += correct(v, len - i - 1);
                return result;
            } else {    // 균형잡힌 괄호 문자열
                result += '(';
                result += correct(v, len - i - 1);
                result += ')';
                result += change(u, i + 1);
                return result;
            }
        }
    }
}

string solution(string p) {
    int len = p.size();
    return correct(p, len);
}

실행 결과

실행 결과 : 100.0