[프로그래머스] 괄호 변환 (2020 KAKAO BLIND RECRUITMENT)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058

 

 

<전체적 알고리즘>

문제 자체에 알고리즘이 완벽하게 주어져 있다. 알고리즘이 주어져있지 않았다면 분명히 어려운 문제겠지만 문제에 알고리즘이 자세히 설명되어있기에 그냥 고민할 것 없이 그대로 구현하면 된다. 알고리즘이 그대로 적혀있기에 굳이 설명할 것 없이 넘어가겠다.

 

 

<올바른 괄호 문자열 확인 알고리즘>

전체적인 알고리즘은 그대로 구현하면 되지만 올바른 문자열인지 아닌지 판별하는 함수는 생각해 보아야 한다. 

 올바른 괄호 문자열 판별은 단순히 스택을 이용해서 알 수 있다. 열린 괄호일 때 stack에 넣어주고 닫힌 괄호일 때 stack에서 빼주면서 쌍을 만들어 준다. 모두 쌍이 만들어지면 올바른 괄호 문자열이다.

 

(코드에서는 stack을 이용하여 구현하였지만 사실 stack을 이용할 필요도 없다. 단순히 변수 count를 이용하여 열린괄호면 count++ 닫힌 괄호면 count--하며 변수하나만으로도 간단히 구현이 가능하지만 좀 더 직관적으로 설명하기 위해 stack을 이용했다.)

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include<iostream> #include<stack> #include<string>   using namespace std;   bool iscorrect(string u)    // 올바른 괄호 문자열인지 확인, 맞는 괄호 짝을 찾아줘야함 {     stack<int> s;           for (int i = 0; i < u.size(); i++)     {         if (u[i] == '(')s.push(u[i]);         else         {             if (s.empty())return false;   //닫힌괄호가 나왔는데 스택이 비어있으면 쌍이없음,,false             s.pop();         }     }     if (!s.empty())return false;   //짝을 다 찾아줬는데 아직 남아있는 괄호있으면 false,,     return true; }   string make_correct(string p)    //올바른 괄호 문자열 만드는 함수 {     if (p.size() == 0)return "";     string u = "";     string v = "";           int balanced = 0;     int i = 0;     for (; i < p.size(); i++)   //u 만들어주기     {         u += p[i];         if (p[i] == '(')balanced++;         else balanced--;           if (balanced == 0)break;      // balanced가 0이되면 균형잡힌 괄호 문자열 완성     }     i++;     for (; i < p.size(); i++)    // v만들어주기     {         v += p[i];     }           if (!iscorrect(u))  //u가 올바른 괄호 문자열이 아니라면     {         string result = "(";         result+= make_correct(v);  //나머지 v에 대해 올바른 괄호 문자열 만들기         result += ")";           string tmp = u.substr(1, u.size() - 2);  //앞뒤 문자떼어버리기         for (int i = 0; i < tmp.size() ;i++)   //문자들 뒤집기         {             if (tmp[i] == '(')tmp[i] = ')';             else tmp[i] = '(';         }                   return result + tmp;   //반환     }     else     {         string result=make_correct(v);  //v에 대해서 올바른 괄호 문자열 만들기         return u + result;   // u랑 합쳐서 반환     } }   string solution(string p) {           string answer = make_correct(p);     return answer; }

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.