2020 카카오 블라인드 공채 문제 2번 설명 및 풀기

 

 

문제 풀러가기

 

 

 

 

완성된 코드

 

 

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

using namespace std;

int index;

bool check(const string& p){
    int left = 0, right = 0;
    bool ret = true;
    stack<char> s;
    
    for(int i = 0; i < p.size(); i++){
        if(p[i] == '('){
            left++;
            s.push('(');
        }else{
            if(s.empty())
                ret = false;
            else
                s.pop();
            
            right++;
        }
        if(left == right){
            index = i + 1;
            return ret;
        }
    }
    return ret;
}

string solution(string p) {
    if(p == "")
        return "";
    
    string u, v;
    bool isCheck = check(p);
    
    u = p.substr(0, index);
    v = p.substr(index);
    
    if(isCheck)
        return u + solution(v);
    
    string answer = "";
    answer += '(';
    answer += solution(v) + ')';
    
    for(int i = 1; i < u.size() - 1; i++){
        if(u[i] == '(')
            answer += ')';
        else
            answer += '(';
    }
    
    return answer;
}

 

다른분들 풀이보면 조건 그대로 만들었다고 하는 글들이 많았습니다.

 

저도 조건에 따라 만들기는 했지만.... 그 조건을 이해하는 것 자체가 힘들었습니다.

 

문제를 읽어도 '이게 무슨말을 하는건가??....' 싶었습니다.

 

때문에 시간도 굉장히 오래걸렸고 많이 답답했습니다.

 

그래서 좀 길게 풀어볼까 합니다. 저 같은 분들을 위해서......

 

 

 

자!! 그럼 하나씩 풀면서 완성시켜 보겠습니다.!!

 

 

#include <string>
#include <vector>

using namespace std;

string solution(string p) {
    if(p == "")
        return "";

    string answer = "";

    
    return answer;
}​

 

말 그대로 입력받은 (string p)값이 빈값이라면 빈 문자열을 반환하는걸 만들었습니다.

 

 

 

 

저는 여기서부터 막혔습니다. 

"u는 더이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다."(뭔 개소리야 이게 ㅡㅡ)

 

 

우선, 문자열 w를 u, v로 나눠 줘야합니다.(여기서 문자열 w는 코드상 p가 됩니다.)

그럼 무슨 기준으로 나누는가??

바로 "균형잡힌 괄호 문자열이 경우"의 기준으로 나눠줍니다.

 

균형잡힌 괄호 문자열의 조건은 다음과 같습니다.

 

 

위 설명을 보면 코드에서 주어진 string p는 무조건 균형잡힌 괄호 문자열로 전달받는 다는걸 알 수 있습니다.

 

string p는 현제 균형잡힌 괄호 문자열 이지만 문제에서 요구하는 "정렬된 문자열"인지는 알 수 없습니다.

 

s = ((())) 이 될수도 있고 s = )))((( 이 될 수도 있고 s = ()))(()()이 될 수도 있습니다.

 

그럼 저희는 이렇게 생각해야 합니다.

 

u에는 최소한 '('와 ')'의 갯수가 같은 곳 까지만 분리하고, 나머지 부분은 일단 v에 넣어두자!!

ex) ) ) ) ( ( ( ( ) 이라고 한다면  ) ) ) ( ( ( || ( ) 이런식으로 분리....(괄호 갯수가 최초로 같은 곳)

 

그럼, 왜 이런 기준으로 굳이 나눠야 하나?? 다른 방법은 없나??

 

문제에서 제시하고 있는 것은 괄호의 정렬 여부입니다. 서로 정갈하게 마주보고 있어야 하죠.

 

그리고 문제에선 이런식으로 문제를 풀라고 예시를 주고 있습니다.

 

즉, 저렇게 나눈 후 문제를 풀라고 말하고 있는거죠.....

 

정답을 맞출려면.... 문제를 따라야죠.....

 

그럼 2번을 코딩해 보겠습니다.!!

 

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

using namespace std;

int index;

bool check(const string& p){
    int left = 0, right = 0;
    bool ret = true;
    stack<char> s;
    
    for(int i = 0; i < p.size(); i++){
        if(p[i] == '('){
            left++;
            s.push('(');
        }else{
            if(s.empty())
                ret = false;
            else
                s.pop();
            
            right++;
        }
        if(left == right){
            index = i + 1;
            return ret;
        }
    }
    return ret;
}

string solution(string p) {
    if(p == "")
        return "";
    
    string u, v;
    bool isCheck = check(p);
    
    u = p.substr(0, index);
    v = p.substr(index);
    
    
    string answer = "";
    return answer;
}​

 

좀 많이 길어졌습니다....

 

2번이 이 코드의 핵심이라서 그렇습니다.....

 

설명하자면........

 

38행에선 string u와 v를 선언해주고 있습니다.

39행에선 check()라는 함수를 호출하고 반환 값은 isCheck변수에 넣고 있습니다.

여기서 check()함수는 위에서 설명했던 "균형잡힌 괄호 문자열"로 나누는 작업을 하는 녀석입니다.

 

9행에 있는 check()함수를 보겠습니다.

우선 괄호의 갯수가 서로 맞는지 확인하기 위해( '('와 ')'의 갯수가 동일한지)

left와 right변수를 선언해 줬습니다.

 

그 후 for문을 통해 '('와 ')'의 갯수를 확인하며 갯수가 동일한 지점에서 값을 반환하고 있습니다.

이때 저희는 p를 나눌 기준이되는 index값이 중요하므로 index를 전역변수로 선언한 후 

left와 right가 같을 때 최종 index 값에 + 1을 해주고 있습니다.

i + 1을 해야 나누기 편합니다.(substr할때 편합니다.)

그럼 왜???!!! index값으로 반환을 안하고 굳이 전연변수로 선언하고 뭔지 모를 bool변수를 반환하는가??!!!

 

여기서 중요한것은 check()함수를 통해 저희는 2가지 사실을 알아야 합니다.

1. p를 u와 v로 나누기 위한 index값.

2. 나눴을 때 u는 올바른 괄호 문자열인지 아닌지 확인을 해야 한다.

 

여기서 올바른 괄호 문자열이란?

 

라고 하내요.....

 

 

어쨋든.....

 

저희는 p의 '('와 ')'의 갯수를 세면서 u로 들어갈 괄호들이 서로 정갈하게 마주보고 있는지, 아닌지를 판단해 줘야합니다.

 

그걸위해 bool ret과 stack<char> s를 선언해 준겁니다.

 

우선 괄호는 무조건 '('가 먼저 와야 올바른 괄호 문자열이 성립할 수 있습니다.

따라서 스택이 빈공간인지 아닌지에 따라 ret의 값이 정해짐니다.

 

만약 스택이 비어있는데 ')'이 왔다??

그런 경우는 ")()(" or "())()(" or (()))(" 이런 경우가 되겠습니다.

즉, 올바른 괄호 문자열이 아니라는 뜻이겠죠....

 

check()함수를 마친 후 u와 v에 p.substr()기능을 사용해 값을 복사해 주고 있습니다.

 

여기까지가 2번까지 된 것입니다.

 

이 문제를 보고 정말 가볍개 풀어내신 분들을 보면 대단하것 같습니다........

 

 

 

자 다음!!! 3번조건 입니다.

 

 

 

저희가 앞서 u = p.substr(0, index), v = p.substr(index)를 진행했습니다.

 

u로 복사된 괄호들이 서로 정갈하게 마주보고 있다면 문자열 v를 가지고 처음부터 다시하란 소리입니다.

 

이게 뭔말이냐????

 

u는 냅두고 v를 가지고 첫단개부터 새롭게 하란 소리입니다.

즉, 저희가 1단계를 만들고 2단계를 만들고 그 과정들을 다시하란 소리입니다.

무엇으로?? 문자열 v로.....

 

하지만 코드를 다시짤 필요는 없습니다. 왜냐?!!

저희가 작성중인 solution()함수 그 자체가 1단계부터 진행되고 있는 함수기 때문에 저희 함수를 다시 불러주면 됩니다.

즉!! 재귀호출 입니다.....

 

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

using namespace std;

int index;

bool check(const string& p){
    int left = 0, right = 0;
    bool ret = true;
    stack<char> s;
    
    for(int i = 0; i < p.size(); i++){
        if(p[i] == '('){
            left++;
            s.push('(');
        }else{
            if(s.empty())
                ret = false;
            else
                s.pop();
            
            right++;
        }
        if(left == right){
            index = i + 1;
            return ret;
        }
    }
    return ret;
}

string solution(string p) {
    if(p == "")
        return "";
    
    string u, v;
    bool isCheck = check(p);
    
    u = p.substr(0, index);
    v = p.substr(index);
    
    if(isCheck)
        return u + solution(v);
    
    string answer = "";
    return answer;
}​

 

 

추가되건 44행과 45행밖에 없습니다.

 

저희는 isCheck라는 변수로부터 문자열을 나눌 때 u에 들어갈 괄호들이

올바른 문자열인지 아닌지를 판단할 수 있었습니다.

 

따라서 44행에서 그것을 확인해주고, 만약 올바른 문자열이라면

3-1번의 조건대로 v에대해 처음부터 실행하고 그 결과를 u에 붙여 반환하는 걸 만든 것입니다.

 

저는 지금 문제에서 요구하고 있는대로 그냥 코드를 작성중에 있는 것입니다.

저도 왜 이렇게 되는지 100%이해는 못하고 있습니다..... 따라서 여기까지 보고 계신 분들이 계신다면...

그런 의구심은 잠시 접고, 조건대로 작성하는 것에 집중하시면 좋을 것 같습니다.

 

 

 

그럼 마지막 4번을 봅시다......

 

 

여긴 정말 쉽습니다. 그냥 고대로 따라해주기면 한다면 됩니다.

 

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

using namespace std;

int index;

bool check(const string& p){
    int left = 0, right = 0;
    bool ret = true;
    stack<char> s;
    
    for(int i = 0; i < p.size(); i++){
        if(p[i] == '('){
            left++;
            s.push('(');
        }else{
            if(s.empty())
                ret = false;
            else
                s.pop();
            
            right++;
        }
        if(left == right){
            index = i + 1;
            return ret;
        }
    }
    return ret;
}

string solution(string p) {
    if(p == "")
        return "";
    
    string u, v;
    bool isCheck = check(p);
    
    u = p.substr(0, index);
    v = p.substr(index);
    
    if(isCheck)
        return u + solution(v);
    
    string answer = "";
    answer += '(';
    answer += solution(v) + ')';
    
    for(int i = 1; i < u.size() - 1; i++){
        if(u[i] == '(')
            answer += ')';
        else
            answer += '(';
    }
    
    return answer;
}
​

 

수정된 부분은 47행부터 56행 까지 입니다.

 

문제에서 제시하는 빈 문자열은 기존에 존재하고 있던 string answer를 사용했습니다.

48행은 4-1번의 조건을 수행하고 있습니다.

49행은 4-2와 4-3번의 조건을 수행하고 있습니다.

문제에서 붙인다라는 표현을 사용했기 때문에 operator += 을 사용했습니다.

 

51행부터 56행까지는 4-4번에 대한 내용입니다.

u문자열의 첫째와 마지막을 제거하라고 했으니, for문을 돌릴 때 첫번째와 마지막을 제외시켰습니다.

어떻게? i = 1, i < u.size() - 1 로 말이죠....

 

그 후 "나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다."(어디 뒤에다 붙이란 소리냐 도대체 ㅡㅡ)

 

u에대해 괄호를 뒤집어 주라고 하고 있으니 반대로 뒤집으면 되고,

 

뒤에 붙이란 소리는 answer 뒤에 붙이란 소리입니다.

이 방법이 51행 ~ 56행이 되겠습니다.

 

마지막 58행은 4-5번에 대한 조건입니다.

 

실행 결과는??!!!

 

 

 

긴 글 보시느라 고생 많으셨습니다.