프로그래머스 _ 괄호 변환

2020-09-11 · 배운 것 · 5분 읽기

programmers.co.kr/learn/courses/30/lessons/60058

코딩테스트 연습 - 괄호 변환

풀이방법

이 문제는 솔루션이 다 주어진다. 진짜로 주어진 조건에 맞춰서 그대로 진짜 그대로~ 하면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;

//check함수
bool CheckStr(string str)
{
    stack<char> dish;

    for (char ch : str)
    {
        //dish가 비어있을때
        if (dish.empty())
        {
            //'('경우
            if (ch == '(')
                dish.push(ch);
            
            //')'경우
            else if (ch == ')')
                return false;
        }

        //dish가 안비어있을때
        else
        {
            //'('경우
            if (ch == '(')
                dish.push(ch);
            //')'경우
            else if (ch == ')')
            {
                if (dish.top() == '(')
                    dish.pop();
                else
                    dish.push(ch);
            }
        }
    }
    if (dish.empty())
        return true;
    
    return false;
}

//두개의 문자열로 분리하는 함수
pair<string, string> SeparateStr(string str)
{
    for (int divNum = 2; divNum <= str.size(); divNum+=2)
    {
        string u = str.substr(0, divNum);
        string v = str.substr(divNum, str.size() - divNum);
        int cnt = 0;
        for (char uch : u)
        {
            if (uch == '(')
                cnt++;
            else
                cnt--;
        }
        //균형잡힌 문자열인 경우
        if (cnt == 0)
        {
            return { u, v };
        }
    }
}

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

    //올바른 균형잡힌 문자열인경우 결과값 return
    if (CheckStr(p) == true)
        return p;

    //1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
    if (p == "")
        return p;

    //2. 문자열이 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다.
    pair<string, string> temp = SeparateStr(p);
    string u = temp.first;
    string v = temp.second;

    //3. u가 올바른 문자열이라면 v는 1단계부터 다시수행!!
    if (CheckStr(u) == true)
        answer = u + solution(v);
    // u가 올바른 문자열이 아니라면 다음 과정을 수행!!
    else
    {
        answer += '(';
        answer += solution(v);
        answer += ')';

        //u의 첫번쨰와 마지막 문자를 제거하고 괄호방향을 뒤집어서 붙인다
        for (int i = 1; i < u.size() - 1; i++)
        {
            char pushCh;
            if (u[i] == '(')
                pushCh = ')';
            else
                pushCh = '(';
            answer += pushCh;
        }
    }

    return answer;
}