[2020 카카오 블라인드 채용 코딩테스트] 괄호 변환 C++ 풀이 및 정답 코드

문제 링크

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

프로그래머스

 

 

 

문제 설명

재귀 문제를 내고 싶던 출제자가 예외 상황 제외하고 구현 범위를 좁히다보니 이런 문제가 나온 것 같다.

재귀를 통해 균형잡힌, 올바른 괄호 문자열을 리턴하는 문제이다.
찬찬히 읽어보면 왜 이런 방식으로 괄호를 해결하는지 알 수 있지만, 마음이 급한 상황에 읽으면 어쩌라고 싶을 것 같다.

문자열을 균형잡힌 가장 작은 문자열인 u를 계속해서 앞에서 분리해서 v가 빈 문자열이 될 때 까지 옳은 문자열이 되도록 방향을 바꿔 뒤에 붙이는 것이다. 

 

 

 

문제 풀이

1. 균형잡힌 가장 작은 괄호 문자열 u와 v를 분리하기
'('와 ')'를 카운트해서 1보다 크면서 같으면 해당 인덱스를 리턴한다.

2. 옳은 괄호 문자열인지 알아내기
stack을 통해 옳은 문자열인지 알아낸다.
그 옛날 알고리즘 시간에 배웠던 게 기억이 난다.

3. 문제 설명대로 재귀함수 작성하기
말 그대로 문제 설명을 따라 로직을 작성하면 된다.
사실 문제를  이해하지 못해도 그대로 구현하면 통과할 것 같다.

 

 

 

코드

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

using namespace std;

int getPosBalanced(string s) {
    int lc = 0;
    int rc = 0;
    int i = 0;
    for (;i<s.length();i++) {
        if (s[i] == '(')
            lc++;
        else 
            rc++;
        if (lc > 0 && lc == rc)
            break;
    }
    return ++i;    
}

bool isRight(string s) {
    stack<char> stack;
    for (auto c : s) {
        if (c == '(')
            stack.push('(');
        else {
            if (stack.empty())
                return false;
            else
                stack.pop();
        }        
    }
    
    return stack.empty();
}

string recursive(string s) {
    // 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
    if (s == "")
        return "";
    
    // 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
    int pos = getPosBalanced(s);
    string u = s.substr(0,pos);
    string v = s.substr(pos);
    
    // 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
    if (isRight(u))
        // 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
        return u + recursive(v);
    // 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
    else {
        // 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
        // 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
        // 4-3. ')'를 다시 붙입니다. 
        string str = "(" + recursive(v) + ")";
        // 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
        for (int i=1; i<u.length()-1; i++) {
            str += u[i] == '(' ? ')' : '(';
        }
        return str;
    }
    
    
}

string solution(string p) {
    string answer = recursive(p);
    return answer;
}

 

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰

삼십분 정도 걸린듯