[프로그래머스] (문자열) 카카오 괄호 변환 c++

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

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

 

문자열을 다루는 문제.

 

기본적인 아이디어

 

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. 생성된 문자열을 반환합니다.

 

 

는 전부 문제에 나와있다.

 

소스코드

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

using namespace std;

bool check(string &p);
string one(string &p);
string two(string &p);


//https://programmers.co.kr/learn/courses/30/lessons/60058
string solution(string p) {
    string answer = "";

    answer=one(p);

    return answer;
}


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


string one(string &p) // 1.
{
    if(p.length()==0)
    {
        return "";
    }
    else
    {
        return two(p);
    }
}

string two(string &p) //2.
{
    string u,v;
    int ln=0;
    int rn=0;
    int ui;
    for(int i=0; i<p.length(); i++)
    {
        if(p[i]=='(')
        {
            ln++;
        }
        else
        {
            rn++;
        }
        
        if(rn==ln)
        {
            ui=i;
            break;
        }
    }
    
    u=p.substr(0,ui+1);
    v=p.substr(ui+1);
    


    if(check(u))//3.
    {
       return u.append(one(v));//3-1.
    }
    else //4.
    {
       
        string temp="(";//4-1.
        temp.append(one(v));//4-2.
        temp.append(")");//4-3.

        
        u.erase(u.begin()); //4-4.
        u.erase(u.end()-1); 
        for(int i=0; i<u.length(); i++)
        {
            if(u[i]=='(') u[i]=')';
            else u[i]='(';
        }
        temp.append(u);
        
        
        return temp; //4-5.
    }
    
}

 

 

자바쓰다가 C++ 쓰니까 문자열 string 다루는게 쉽지 않다.기억해둬서 유용하게 써먹자.

 

erase

str.erase (idx, count);  // index부터 count갯수 만큼 제거
str.erase(str.begin());  // str 맨 처음 제거
str.erase(str.end()-1);  // str 맨 뒤 제거

 

substr

str1.substr(idx);        // index 부터 끝까지 반환
str1.substr(idx, count); // index 부터 count 갯수 반환