프로그래머스 카카오, 괄호 변환 C++ [CPP] ★★★

문자열 처리에 애를 먹었다.

조건이 정말 까다로웠다.

난 그랬다.

 

 

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

 

---

 

#맞는 풀이

#include <bits/stdc++.h>

using namespace std;

//나눌 수 없는 균형잡힌 문자열 => position
//그것이 올바른지 아닌지 return
bool IsCorrect(string str, int* pos){
    bool isCorrect = true;
    int open = 0;
    int close = 0;
    stack<char> stk;
    
    for(int i = 0; i<str.length(); i++){
        if(str[i] == '(') {
            stk.push(str[i]);
            open++;
        }
        else{
            close++;
            if(stk.empty()){
                isCorrect = false;
            }else{
                stk.pop();
            }
        }
        
        //분리할 수 없는 가장 작은 균형잡힌 문자열 => 해당 위치를 찾았으니 종료
        if(open == close){
            *pos = i + 1;
            return isCorrect;
        }
    }
    
    return true;
    
    
}

string solution(string p) {
    if(p.empty()) return p; //조건 1
    
    //p는 항상 균형잡힌 문자열임. => 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
    //u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
    //u는 분리할 수 없어야함 => 가장 작은 균형잡힌 괄호 문자열을 찾아야함.
    
    
    int pos; //문자열 p에 대한 [0,pos)까지의 문자열 => pos로 u와 v를 나눌 수 있음.
    bool isCorrect = IsCorrect(p, &pos);
    
    //조건2
    string u = p.substr(0, pos);
    string v = p.substr(pos);
    
    //조건 3
    if(isCorrect){
        return u + solution(v);
    }
    
    //조건 4-1~3
    string answer = "(" + solution(v) + ")";
    
    //조건 4-4
    for(int i = 1; i<u.length() - 1; i++){
        if(u[i] == '(') answer += ")";
        else answer += "(";
    }
    
    //조건 4-5
    return answer;
}

이건 하고나서야.. 쉬운 것이지

처음엔 조건이 뭔지 하나도 감이 안왔다.

내일 다시 보면서 풀어봐야겠다.

 

---

 

# 일어나서 다시 짠 풀이

개판 났다. 깔끔하지는 않다.

그리고 기억이 남아있어서.. 그냥 그렇다.

#include <bits/stdc++.h>

using namespace std;

void Balanced(string str, int* pos){
    int open = 0;
    int close = 0;
    
    for(int i = 0; i<str.length(); i++){
        if(str[i] == '('){
            open++;
        }
        else {
            close++;
        }
        
        
        if(open == close){
            *pos = i + 1;
            return;
        }
    }
}

bool IsCorrect(string str){
    stack<char> stk;
    for(char c : str){
        if(c == '(') {
            stk.push(c);
        }
        else{
            if(stk.empty())return false;
            stk.pop();
        }
    }
    if(!stk.empty())return false;
    
    return true;
    
}


string solution(string p) {
    if(p.empty()) return p;
    
    int pos;
    Balanced(p, &pos);
    
    string u = p.substr(0,pos);
    string v = p.substr(pos);
    
    if(IsCorrect(u)){
        return u + solution(v);
    }
    
    string answer = "(" + solution(v) + ")";
    for(int i = 1; i<u.length()-1; i++){
        if(u[i] == '('){
            answer += ")";
        }
        else {
            answer += "(";
        }
    }
    

    return answer;
}