백준 2504번 - 괄호의 값 (C++)

문제

 

구현 방법

각 괄호마다 괄호 내부의 숫자들을 곱해주기 위하여 재귀를 통하여 구현했다. 크게 세 단계로 구성되어있으며, 먼저 붙어있는 괄호들을 A2B/A3B형식으로 숫자로 바꾸어준다. AB는 2 3 이 23인지 2와 3인지 숫자끼리 구분하기 위하여 덧붙였다. 그리고 이 과정에서 괄호의 갯수를 세며 존재가 불가능한지 판단한다.

이후 재귀를 돌며 괄호를 만나면 해당 괄호가 끝날때까지 그 사이에 있는 A?B에 괄호별 값을 곱해준다. 이때 string에서의 곱 이기 때문에 정수로 변환 후 곱한 후 해당 결과를 삭제->중간 삽입 하는 과정을 거쳐서 곱연산을 하게 되었다. 이를 재귀로 반복하여 문자열의 끝까지 있는 모든 괄호에 대하여 연산을 마치고, 이후 다시 순회하며 모든 숫자들을 더해준다

 

아쉬웠던점

중간 삽입/삭제가 없어도 가능할 것 같다. 대충 생각해봐도 자릿수는 하나 이상으로 늘어나지 않으니 기존에는 값을 변경해주고 자릿수가 바뀌면 삽입만 해줬어도 삭제는 필요 없었던 것 같다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
void MytFind(string &_str, int _Num, char _Char = 'D')
{
    _str[_Num] = 0; //앞으로 탐색 불가능하도록 괄호 0만들기 
    for (_Num++; _Num < _str.size(); ++_Num)
    {
        string _StrMax;
        //괄호 시작 찾으면 재귀 돌림.
        if (_str[_Num] == '(' || _str[_Num] == '[')
        {
            MytFind(_str, _Num, _str[_Num]);
            if (_Char == 'D')
                return;
        }
        //괄호 끝 찾으면 해당 함수 종료.
        else if (_str[_Num] == ']' || _str[_Num] == ')')
        {
            if (_Char == 'D')
                return;
            _str[_Num] = 0; //끝괄호 0만들기
            _Char = 'D';
        }
        //숫자 찾으면 곱해줌.
        else if (_str[_Num] == 'A' && _Char != 'D')
        {
            int i;
            //숫자 찾기
            for (i = _Num+1; i < _str.size(); ++i)
            {
                if (_str[i] == 'B')
                    break;
                _StrMax += (int)_str[i];
            }
            //자릿수 늘어날 경우 고려.
            if (_Char == '(')
                _StrMax = to_string(stoi(_StrMax) * 2);
            else
                _StrMax = to_string(stoi(_StrMax) * 3);
            _str.erase(_Num, i-_Num+1);
            _str.insert(_Num, "A" + _StrMax + "B");
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string Str;
    cin >> Str;
 
    int Start = 0, End = 0, Start_1 = 0, End_1 = 0, Max = 0, First = -1;
 
    //1. 한번 순회하며 초기 숫자 세팅.
    for (int i = 0 ; i < Str.size(); ++i)
    {
        if (Str[i] == '(')
        {
            if (Str[i + 1] == ')')
            {
                Str.erase(i, 2);
                Str.insert(i, "A2B");
            }
            else
            {
                ++Start;
                if (First == -1)
                    First = i;
            }
        }
        else if (Str[i] == ')')
        {
            --Start;
        }
        else if (Str[i] == '[')
        {            
            if (Str[i + 1] == ']')
            {
                Str.erase(i, 2);
                Str.insert(i, "A3B");
            }
            else
            {
                ++Start_1;
                if (First == -1)
                    First = i;
            }
        }
        else if (Str[i] == ']')
        {
            --Start_1;    
        }
 
        if (Start_1 < 0 || Start < 0)
        {
            cout << "0";
            return 0;
        }
    }
 
    if (Start != 0 || Start_1 != 0)
    {
        cout << "0";
        return 0;
    }
 
    //2. 재귀 돌며 괄호 풀어줌.
    if (First != -1)
        MytFind(Str, First, Str[First]);
 
    //3. 재귀를 통하여 변환된 숫자들 합치기
    for (int i = 0 ; i < Str.size() ; ++i)
    {
        if (Str[i] == 'A')
        {
            string NumStr = "0";
            for (int j = i + 1; j < Str.size(); ++j)
            {
                if (j == 'B')
                    break;
                NumStr += Str[j];
            }
            Max += stoi(NumStr);
        }
    }
    cout << Max;
}

잡설

특정 상황에서 범위 밖 접근으로 터지는데 백준에서 이게 "틀렸습니다"로 뜨는줄 모르고 많이 삽질했다 ㅠㅠ 컴파일에러든 뭐든 다르게 나올줄 알고 틀렸습니다는 당연히 뭔가 다른게 있는줄 ㅠㅠ