2020 KAKAO BLIND RECRUITMENT-괄호 변환-C++

이번문제는 문자열 처리 문제입니다.
문제 해결방법을 카카오측에서 제시를 하였기 때문에, 그대로 구현하면 되는 문제였습니다.

괄호변환 바로가기

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
   3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
   4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
   4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
   4-3. ')'를 다시 붙입니다.
   4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
   4-5. 생성된 문자열을 반환합니다.

해당문제의 풀이과정을 이미 적어놨기 때문에, 그대로 구현을 하면 되었습니다.

함수는 check divide correct 함수 세개를 만들었습니다.

• check 함수, 문자열을 검사하는 함수
• divide 함수, u와 v로 나누는 함수
• correct 함수, 이 문자열이 올바른 함수인지 검사하는 함수

순서대로 확인해보겠습니다.

check

string check(string s){
//1번 입력이 빈 문자일경우, 빈문자열 반환
    if(s.size()==0){
        return "";
    }
    
    string u = "";
    string v = "";
    
    //2번 문자열 w를 u,v로 분리
    divide(u,v,s);
    
    //3번 문자열 u가 올바른 문자열일경우 if문 실행, 아니면 else문 실행
    if(correct(u)){
    //만약 올바른 문자일 경우 v를 다시 check의 인자로 넣어서 다시 1부터 수행
        string x = check(v);
        //3-1 수행한 결과 문자열을 u에 이어붙인후 반환
        return u+x;
    }else{
    //4번 u가 올바른 문자열이 아닌경우 수행
        string tmp="";
        //4-1 빈문자열에 첫번째 문자로 (붙이기
        tmp+='(';
        //4-2 문자열 v에 대해서 check의 인자로 넣어서 1번부터 재귀적으로 수행
        string x = check(v);
        //4-2그리고 tmp에 이어붙임
        tmp +=x;
        //4-3 )를 이어서 붙임
        tmp +=')';
        //4-4 substr를 통해서 맨 처음과 끝문자를 지운 newU를 생성
        string newU = u.substr(1, u.length() - 2);
        //4-4 나머지 문자열 괄호 방향 뒤집기
        for(int i=0;i<newU.size();i++){
            if(newU[i]=='('){
                newU[i]=')';
            }else{
                 newU[i]='(';
            }
        }
        //이어붙이고 반환
        tmp+=newU;
        return tmp;
    }
}

divide

void divide(string & u, string & v, string &s){
    int count1=0;
    int count2=0;
    int i=0;
    for(i=0;i<s.size();i++){
        if('('==s[i]){
            count1++;
        }else{
            count2++;
        }
        
        u+=s[i];
        
        if(count1==count2){
            break;
        }
    }
    for(int j=i+1;j<s.size();j++){
        v+=s[j];
    }
}

divide의 해석이 처음에 약간 이상했는데 균형잡혔다면 어디서부터 시작인거지? 또 언제 끝내야하는거지? 정확한 내용을 설명해주지않았는데,
처음부터 시작해서 (의 갯수와 )의 갯수가 동일할때 그때가 균형잡힌입니다.

그래서 count1과 count2로 나누어 갯수를 각각세주고, 동일하면 break후 나머지는 v에다가 담았습니다.

correct

bool correct(string tmp){
    stack<char> s;
    s.push(tmp[0]);
    
    for(int i=1;i<tmp.size();i++){
        if(tmp[i]==')' && s.size()>0 && s.top()=='('){
            s.pop();
        }else{
            s.push(tmp[i]);
        }
    }
    
    if(s.size() == 0){
        return true;
    }else{
        return false;
    }
}

올바른 문자열인지 판단하기 위해서 stack을 만들고, 맨위가 (인데 )를 넣어야되면
s.pop으로 지우고,
만약에 다 수행했는데 stack의 크기가 0이면 올바른 문자열 아니면 false입니다.

정답코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;

bool correct(string tmp){
    stack<char> s;
    s.push(tmp[0]);
    
    for(int i=1;i<tmp.size();i++){
        if(tmp[i]==')' && s.size()>0 && s.top()=='('){
            s.pop();
        }else{
            s.push(tmp[i]);
        }
    }
    
    if(s.size() == 0){
        return true;
    }else{
        return false;
    }
}

void divide(string & u, string & v, string &s){
    int count1=0;
    int count2=0;
    int i=0;
    for(i=0;i<s.size();i++){
        if('('==s[i]){
            count1++;
        }else{
            count2++;
        }
        
        u+=s[i];
        
        if(count1==count2){
            break;
        }
    }
    for(int j=i+1;j<s.size();j++){
        v+=s[j];
    }
}

string check(string s){
    if(s.size()==0){
        return "";
    }
    
    string u = "";
    string v = "";
    
    divide(u,v,s);
    
    if(correct(u)){
        string x = check(v);
        return u+x;
    }else{
        string tmp="";
        tmp+='(';
        string x = check(v);
        tmp +=x;
        tmp +=')';
        string newU = u.substr(1, u.length() - 2);
        for(int i=0;i<newU.size();i++){
            if(newU[i]=='('){
                newU[i]=')';
            }else{
                 newU[i]='(';
            }
        }
        tmp+=newU;
        return tmp;
    }
}

string solution(string p) {
    string answer = "";
    if(correct(p)){
        answer+=p;
        cout<<"correct";
    }else{
        cout<<"not correct";
        answer += check(p);
    }
    
    return answer;
}

문제 총평
난이도: 하
카카오 문제 LV3를 풀면서 하나도 풀지못해 자괴감이 빠져, 회복을 위해서 Lv2를 풀었다.
lv2는 확실히 쉬운듯..
문제푸는데 30분도 안걸렸다.
-THE END-