[BOJ] 2504 : 괄호의 값 / C++

SW마에스트로 합격을 위해 최근 열심히 코딩 테스트를 준비하고 있다.

열심히 코테를 위한 뇌를 깨우고 있던 중, 첫 번째 난관에 봉착했다.

꽤나 오랜 시간을 투자한 만큼 더이상 삽질하지 말자는 의미에서, 기존 내가 설계했던 방식에 대한 짧은 소개와 문제점, 그리고 올바른 풀이를 설명하고자 한다.

이번 문제에서는 아이디어만큼 내가 여기서 겪었던 실패와 성공의 경험 역시 중요하다고 생각해 전반적인 흐름을 작성하였으니, 하나의 이야기를 보는 느낌으로 편하게 봐 주시면 될 것 같다.

 

문제

https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

 

아이디어(그런데 실패를 곁들인)

전반적인 흐름은 stack 활용의 대표 문제 격인 괄호 쌍 찾기를 이용하였고, 세부 구현은 중첩된 if문을 통해 완료하였다. 최종 결과인 res에 더해줄 임시 변수값인 addNum을 선언해 주었고, ) 또는 ] 문자를 만나면 해당 괄호쌍의 기능을 파악하여 적절한 처리를 해 주고자 하였다.

1. 괄호쌍이 서로 붙어 있으면 addNum에 2 또는 3을 더해 주고, 괄호쌍이 서로 떨어져 있으면 addNum에 값을 곱해 준다.

2. 1번의 기능 수행 후 stack이 empty라면 해당 괄호쌍은 완전히 종료되었다는 뜻이므로 res에 addNum을 더하고, addNum을 초기화한다.

3. 위의 과정 반복, 최종적으로 res를 출력한다(물론 예외 처리에 대한 구현도 포함)

 

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

string s;
stack<char> stc;
int res;
int addNum;

int minusNum;

void getExit()
{
    cout << "0";
    exit(0);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;

    for (int i{0}; i < s.length(); i++)
    {
        if (s[i] == ')')
        {
            if (stc.empty() || stc.top() != '(')
                getExit();

            int topChar = stc.top();
            stc.pop();

            if (s[i - 1] == '(')
            {
                if (!stc.empty() && (s[i + 1] == '(' || s[i + 1] == '[') && (s[i + 2] == '(' || s[i + 2] == '['))
                    minusNum += 2;
                addNum += 2;
            }
            else
                addNum *= 2;

            if (stc.empty())
            {
                res += addNum;
                if (topChar == '(')
                    res -= minusNum * 2;
                else
                    res -= minusNum * 3;

                addNum = 0;
                minusNum = 0;
            }
        }
        else if (s[i] == ']')
        {
            if (stc.empty() || stc.top() != '[')
                getExit();

            int topChar = stc.top();
            stc.pop();

            if (s[i - 1] == '[')
            {
                if (!stc.empty() && (s[i + 1] == '(' || s[i + 1] == '[') && (s[i + 2] == '(' || s[i + 2] == '['))
                    minusNum += 3;
                addNum += 3;
            }

            else
            {
                minusNum *= 2;
                addNum *= 3;
            }

            if (stc.empty())
            {
                res += addNum;
                if (topChar == '(')
                    res -= minusNum * 2;
                else
                    res -= minusNum * 3;

                addNum = 0;
                minusNum = 0;
            }
        }
        else
            stc.push(s[i]);
    }

    if (!stc.empty())
        getExit();
    cout << res;
}

 

실패의 원인 -  가중치 처리

앞서 설명한 로직 외에, minusNum을 비롯한 추가적인 구현이 보일 것이다.

이 구현을 추가한, 그리고 해당 코드가 결과적으로 틀린 이유는 간단하다.

1) "( ) [ [ ] ]"와 같은 괄호쌍은 정상적으로 계산하지만,

2) "( ( ) [ [ ] ] )"와 같이 중첩된 괄호쌍에선 addNum값이 초기화되기 전까지는 계속해서 원치 않는 가중치가 붙기 때문이다.

 

가령, 2)에서 첫 번째 괄호쌍 "( )"은 +2로 기능하여 실제로 addNum값에 2가 추가된다.

하지만 이 값은 뒤의 "[ [ ] ]"의 바깥쪽 괄호쌍을 계산할 때 *3을 거쳐 +6이 되고, 이후 마지막 가장 큰 괄호쌍을 지나칠 때 또 *2가 되어

결과적으로는 res에 +12의 값, 의도한 +4와는 다른 +8의 가중치를 가지게 되어 잘못된 결과를 초래하게 되는 것이다.

 

그래서 해당 문제를 인지한 후 별도의 minusNum 변수를 할당하여 가중치가 붙을 때마다 minus해주는 값도 크게 만들어 최종적으로 가중치를 상쇄하고자 하였으나, 결과적으로는 실패하고 말았다.

 

 

---

 

아이디어(이제는 성공을 곁들인)

재충전의 시간을 가지고 경건하게 다시 로직을 짜 보았고, 전날 설계의 유일한 흠이었던 '가중치' 문제를 다시금 상기해 보았다.

지금까지는 붙어있는 괄호쌍이 주어질 때 해당 값을 바로 더해 주지 않고 addNum에 저장하고 있다가 미래에 더해 주었는데, 문득 '이렇게까지 할 필요가 있나?' 라는 생각이 들었다.

만약 현재 그 값을 바로 더한다면? 그리고 그 값은 지금 바로 더할 수 있지 않는가? 바로 현재 몇중첩의 괄호 속에 있는지.

1. () 또는 [] 쌍을 발견했을 때, 해당 값이 실제로는 몇의 값을 가지게 하는지를 결정할 multiple 변수를 선언한다.

2. multiple 변수는 ( 를 발견했을 때는 2배, [ 를 발견했을 때는 3배의 값을 가진다.

3. ) 또는 ] 를 발견했을 때는 괄호쌍이 종료된 것이므로 2.로 증가된 값을 정상화시킨다.

 

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

string s;
stack<char> stc;

int multiple = 1;
int res;

void getExit()
{
    cout << "0";
    exit(0);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> s;

    for (int i{0}; i < s.length(); i++)
    {
        if (s[i] == ')')
        {
            if (stc.empty() || stc.top() != '(')
                getExit();

            if (s[i - 1] == '(')
            {
                stc.pop();
                res += multiple;
                multiple /= 2;
            }
            else
            {
                stc.pop();
                multiple /= 2;
            }
        }
        else if (s[i] == ']')
        {
            if (stc.empty() || stc.top() != '[')
                getExit();

            if (s[i - 1] == '[')
            {
                stc.pop();
                res += multiple;
                multiple /= 3;
            }
            else
            {
                stc.pop();
                multiple /= 3;
            }
        }
        else
        {
            stc.push(s[i]);
            if (s[i] == '(')
                multiple *= 2;
            else
                multiple *= 3;
        }
    }

    if (!stc.empty())
        getExit();

    cout << res;
}

 

전날에도 많은 시간을 투자했고, 다음날에도 일어나자마자 풀이를 볼까 생각했지만 작은 용기를 내어 시작한 재도전이 좋은 결실을 맺게 되어 뿌듯하다.

 

피식대학 사랑해요