(프로그래머스 C++) 괄호 변환

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60058

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

이 문제는 지문을 대충 읽고 풀었다가는 틀릴 가능성이 높은 문제이다.

---

먼저 문제의 조건은 다음과 같다. 

1. 균형잡힌 문자열 -> '('와 ')'의 갯수가 동일함

ex : '))(('는 균형잡힌 문자열이다.

 

2. 올바른 문자열 -> '('와 ')'의 쌍이 맞아떨어짐

ex : '()'는 올바른 문자열이다.

---

문제 풀이는 다음과 같다.

1. 문자열의 처음과 끝까지 for문을 돌려 균형잡힌 문자열 u와 균형잡힌 문자열 v로 나눈다.

이때 u는 균형잡힌 문자열로 더 이상 분리가 불가능해야한다.

2. 만약 u가 올바른 문자열이라면, 그대로 정답에 이어붙여주고 남은 v에 대해 1번의 과정을 재귀해준다.

3. 만약 u가 올바른 문자열이 아니라면, 우선 정답에 '('를 붙여준다.

3-1. v에 대해 1번의 과정을 재귀해준다.

3-2. 정답에 ')'를 붙여준다. 

3-3. 이로써 3번의 u에 대해 처음과 마지막에 대한 괄호는 고정적으로 붙였다.

u의 첫 번째 자리와 마지막 자리를 제외한 나머지에 해당하는 부분들은 괄호를 뒤집어서 그대로 이어붙여준다.

 

3번부터 3-3까지가 핵심이며, 이 부분은 이해가 가지 않을 경우 공식을 직접 손으로 적어서 이해하는 것을 권장한다.

---

#include <string>
#include <vector>

using namespace std;
string answer = "", samp = "";

void check(string s){
    if(s=="") return;
    int temp = 0;
    for(int i=0; i<s.size(); i++){
        if(s[i]=='(') temp++;
        else temp--;
        if(temp==0){ // 균형잡힌 문자열 u가 나옴
            if(s[0]=='('){ // 동시에 올바른 문자열임
                for(int j=0; j<=i; j++) answer += s[j]; // u를 그대로 갖다 붙임
                samp = "";
                for(int j=i+1; j<s.size(); j++) samp += s[j];
                check(samp); // 나머지 문자 v에 대해 재귀 진행
            }
            else{ //올바른 문자열은 아님
                answer += '('; // 첫째 자리는 무조건 '('
                samp = "";
                for(int j=i+1; j<s.size(); j++) samp += s[j];
                check(samp); // 나머지 문자 v에 대해 재귀 진행
                answer += ')'; // 마지막 자리는 무조건 ')'
                for(int j=1; j<=i-1; j++){ // u의 처음과 마지막을 제외하고 뒤집어서 붙임
                    if(s[j]=='(') answer += ')';
                    else answer += '(';
                }
            }
            return;
        }
    }
}

string solution(string p) {
    check(p);
    return answer;
}

 

 

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.96MB)
테스트 2 〉	통과 (0.01ms, 3.86MB)
테스트 3 〉	통과 (0.01ms, 3.9MB)
테스트 4 〉	통과 (0.01ms, 3.91MB)
테스트 5 〉	통과 (0.01ms, 3.94MB)
테스트 6 〉	통과 (0.02ms, 3.95MB)
테스트 7 〉	통과 (0.01ms, 3.95MB)
테스트 8 〉	통과 (0.01ms, 3.96MB)
테스트 9 〉	통과 (0.01ms, 3.93MB)
테스트 10 〉	통과 (0.01ms, 3.97MB)
테스트 11 〉	통과 (0.01ms, 3.9MB)
테스트 12 〉	통과 (0.01ms, 3.96MB)
테스트 13 〉	통과 (0.01ms, 3.98MB)
테스트 14 〉	통과 (0.02ms, 3.97MB)
테스트 15 〉	통과 (0.02ms, 3.95MB)
테스트 16 〉	통과 (0.05ms, 3.9MB)
테스트 17 〉	통과 (0.03ms, 3.96MB)
테스트 18 〉	통과 (0.07ms, 3.95MB)
테스트 19 〉	통과 (0.13ms, 3.95MB)
테스트 20 〉	통과 (0.10ms, 3.95MB)
테스트 21 〉	통과 (0.04ms, 3.79MB)
테스트 22 〉	통과 (0.03ms, 3.98MB)
테스트 23 〉	통과 (0.07ms, 3.93MB)
테스트 24 〉	통과 (0.02ms, 3.96MB)
테스트 25 〉	통과 (0.03ms, 3.97MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0