[알고리즘] 프로그래머스_괄호 변환

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 균형잡힌 형태의 올바른 괄호를 만드는 문제이다.
• 근데 4-4 ~ 4-5 조건이 한번만 하게 되므로 어떤 결과는 올바른 문자열이 안 될것 같다.

2. 문제 풀이 과정(삽질)

• string 라이브러리를 다루는게 익숙하지 않다.
• 많이 써보고 활용법을 익혀야겠다.

3. 문제 해결

• 조건을 순차적으로 따라서 코드를 짜주었다.
• 재귀 함수로 구현했고, 균형잡힌 괄호(u)를 얻는 것(getU)과 올바른 괄호인지 확인(isPerfect)하는 함수는 따로 만들었다.

4. 코드

#include <string>
#include <vector>
#include <utility>

using namespace std;

string getU(string s)
{
    string u(s, 0, 1);
    int open = (u == "("), close = !open;
    
    for(int i = 1; i < s.length(); i++)
    {
        u += s[i];
        open += s[i] == '(';
        close += s[i] == ')';
        if(open == close)
            return u;
    }
}

bool isPerfect(string s)
{
    int check = 0;
    for(int i = 0; i < s.length(); i++)
    {
        check += s[i] == '(';
        check -= s[i] == ')';
        if(check < 0)
            return false;
    }
    
    return true;
}

string reverseBracket(string s)
{
    for(int i = 0; i < s.length(); i++)
        s[i] = (s[i] == ')') ? '(' : ')';
    return s;
}

string getUV(string s)
{
    if(s == "")
        return s;
    
    string u = getU(s);
    string v(s, u.length(), s.length() - u.length());
    if(isPerfect(u))
    {
        v = getUV(v);
        return u + v;
    }
    else
        return "(" + getUV(v) + ")" + reverseBracket(u.substr(1, u.length() - 2));
}

string solution(string p) {
    string answer = getUV(p);

    return answer;
}

5. 고수의 코드를 보고 배우기

• 코드가 간결해 보인다.
• 문자열을 나눠주는 것도 변수 하나로 판단하여 나눠주고, 재귀함수도 solution 자체가 함수니까 재귀로 처리해줬다.
• 이 코드 외에도 나처럼 함수로 따로 구현해 놓은게 있는데, 함수 명을 보니 문제에 맞게 작명을 할 필요가 있을 것 같다.
  • isBalance(), isCorrect() ...

#include <bits/stdc++.h>
using namespace std;

bool check(const string &a) {
    int r = 0;
    for (char ch : a) {
        if (ch == '(') ++r;
        else --r;
        if (r < 0) return false;
    }
    return r == 0;
}
string solution(string p) {
    if (p == "") return "";
    if (check(p)) return p;

    int i, t = 0;
    for (i = 0; i < p.size(); ++i) {
        if (p[i] == '(') ++t;
        else --t;
        if (t == 0) break;
    }

    string u = p.substr(0, i + 1);
    string v = p.substr(i + 1);

    if (check(u)) return u + solution(v);

    for (char &ch : u) ch = ch == '(' ? ')' : '(';
    return string("(") + solution(v) + ")" + u.substr(1, u.size() - 2);
}