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

문제

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

 

이 때, 주어진 문자열이 균형잡힌 괄호 문자열인지, 올바른 괄호 문자열인지를 확인해야 하므로, 이 경우는 각각 isCorrectString() 와 returnBalanceStringIndex() 함수로 작성했다.

 

bool isCorrectString(string balanace_string) 는 올바른 괄호 문자열일 때는 true를 올바르지 않은 괄호 문자열일 때는 false를 반환하는 함수로서, 열린 괄호( (는 + )와 닫힌 괄호( )는 - )의 수(check)를 카운트하면서 판단한다. 수의 개수만 같으면 안되고(예를 들어, ))((의 경우도 있을 수 있음) 매 순간 열린괄호 (가 먼저 있는지를 확인하기 위해 -가 한번이라도 나와서 check 변수가 음수가 되면 바로 false를 반환하는 함수로 짰다.

 

int returnBalanceStringIndex(string original_string) 는 균형잡힌 괄호 문자열인지를 판단하여 균형잡힌 괄호 문자열까지의 index를 반환하여 u, v로 나누도록 하는 함수이다. 균형잡힌 괄호는 열린괄호와 닫힌 괄호의 수만 맞으면 되므로, 문자열의 0 index부터 마지막까지 반복문을 돌면서 check 변수가 0이 될 때 현재 index를 반환하도록 했다.

 

균형잡힌 문자열 u, v로 나누는 부분은 아래와 같다.

balance_string1 = original_string.substr(0, returnBalanceStringIndex(original_string) + 1);
balance_string2 = original_string.substr(balance_string1.length());

original_string.substr(0, returnBalanceStringIndex(original_string) + 1) 는
0부터 균형잡힌 괄호문자열인데 까지를

 

original_string.substr(balance_string1.length()) 는 균형잡힌 괄호문자열 balance_string1 다음부터 끝까지를 나타낸다.

 

나머지는 문제에서 주어진 방법을 차례로 적은 것 밖에 없고,

 

//★ 4 - 4. balance_string1의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙임
balance_string1 = balance_string1.substr(1, balance_string1.length() - 2);

 

이 부분은 첫 번째와 마지막 문자를 제거 할 수 있는 게 핵심이었는데, balance_string1.substr(1, balance_string1.length() - 2) 이렇게 하니까 () 처럼 length가 2인 경우에도 "" 만 반환하는 것을 확인할 수 있었다. 아마도 인덱스가 잘못(?)되면 or 뒤 매개변수가 적으면 ""를 반환하는 듯 하다.

 

코드

#include <string>
#include <iostream>
using namespace std;

bool isCorrectString(string balanace_string) {
    if (balanace_string == "") return true;

    int check = 0; // ( 는 +1로 )는 -1로 표현해서 괄호개수확인을 통해 올바른 괄호문자열인지를 판단한다.
    for (int i = 0; i < balanace_string.length(); i++) {
        if (check < 0) return false; //한번이라도 음수가 되면 )괄호가 먼저 열린 것이므로 false를 리턴한다.
        check += (balanace_string[i] == '(') ? 1 : -1;
    }return check == 0 ? true : false; //마지막에 check 변수가 0이 되면 올바른 괄호문자열인 것!
}

int returnBalanceStringIndex(string original_string) {
    int check = 0; // ( 는 +1로 )는 -1로 표현해서 괄호개수확인을 통해 올바른 괄호문자열인지를 판단한다.
    for (int i = 0; i < original_string.length(); i++) {
        check += (original_string[i] == '(') ? 1 : -1;
        if (check == 0) return i;
    }return original_string.length();
}

string solution(string original_string) {    
    //1. 입력이 빈 문자열이거나 올바른 문자열인 경우, 그대로 반환
    if (original_string == "" || isCorrectString(original_string)) {
        return original_string; 
    }

    //입력 문자열이 올바른 문자열이 아니라서 괄호 변환이 필요한 경우
    //2. 문자열을 두 "균형잡힌 괄호 문자열" balance_string1, balance_string2로 분리
    string balance_string1 = "", balance_string2 = "";
    balance_string1 = original_string.substr(0, returnBalanceStringIndex(original_string) + 1);
    balance_string2 = original_string.substr(balance_string1.length());

    //3. 문자열 balance_string1가 "올바른 괄호 문자열" 이라면 문자열 balance_string2에 대해 1단계부터 다시 수행
    if (isCorrectString(balance_string1)) {
        //3-1. 수행한 결과 문자열을 balance_string1에 이어 붙인 후 반환
        balance_string1 += solution(balance_string2);
        return balance_string1;
    }

    //4. 문자열 balance_string1가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행
    else {
        string correct_string = "";

        //4 - 1. 빈 문자열에 첫 번째 문자로 '('를 붙임
        correct_string += "(";

        //4 - 2. 문자열 balance_string2에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙임
        correct_string += solution(balance_string2);

        //4 - 3. ')'를 다시 붙임
        correct_string += ")";

        //★ 4 - 4. balance_string1의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙임
        balance_string1 = balance_string1.substr(1, balance_string1.length() - 2);

        for (int i = 0; i < balance_string1.length(); i++) {
            balance_string1[i] = (balance_string1[i] == '(') ? ')' : '(';
        }
        correct_string += balance_string1;

        //4 - 5. 생성된 문자열을 반환
        return correct_string;
    }
}

//test용 코드 추가..
int main() {
    string original_string = "";
    cin >> original_string;
    cout << solution(original_string);
}