[프로그래머스] 괄호 변환

 

 

 

 

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

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

 

 

 

 

이번 문제는 구현 문제였습니다.

 

 

 

 

《문제 풀이》

 

1. 문자열 p가 올바른 괄호 문자열이거나 빈 문자열이면 문자열 그대로 반환

2. 문자열 p가 올바른 괄호 문자열이 아니라면

     (1) 문자열 p를 두 균형잡힌 괄호 문자열 u, v로 분리 ← cnt 변수 이용

     (2) 문자열 u가 올바른 괄호 문자열이면 u + solution(v) 반환

      • 문자열 u가 올바른 괄호 문자열이 아니면

          ▶ '(' + solution(v) + ')' + 첫 번째와 마지막 문자를 제거하고 나머지 문자열의 괄호 방향을 뒤집은 문자열 u 반환

 

 

 

 

 

《C++ 코드》

 

#include <string>
#include <stack>

using namespace std;

// 균형잡힌 괄호 문자열인지 올바른 괄호 문자열인지 체크하는 함수
bool check(string p) {
    stack<char> s;
    
    for (char c : p) {
        if (c == '(') {
            if (s.empty() || s.top() == '(')
                s.push(c);
        } else {
            if (!s.empty() && s.top() == '(')
                s.pop();
        }
    }
    
    if(s.empty()) return true;
    return false; 
}

string solution(string p) {
    string answer = "";
    string u = "";
    string v = "";
    int cnt = 0;
    
    if (p == "" || check(p))
        return p;
    
    // 문자열 p를 두 균형잡힌 괄호 문자열 u, v로 분리
    for (int i=0; i<p.size(); i++) {
        if (p[i] == '(') cnt++;
        else cnt--;
        
        if (cnt == 0) {
            u = p.substr(0, i+1);
            v = p.substr(i+1);
            break;
        }
    }
    
    if (check(u)) return u + solution(v);
    
    answer = '(' + solution(v) + ')';
    for (int i=1; i<u.size()-1; i++) 
        answer += u[i] == '(' ? ')' : '(';
    
    return answer;
}

 

 

 

 

 

프로그래머스 - 정답 화면