1541 잃어버린 괄호

1541. 잃어버린 괄호 / c++ / Silver2 / 1시간

문제 및 코드

문제 및 기존에 풀었던 코드

새로운 코드

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

queue<char> OperQueue;
queue<int> NumberQueue;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    string Input;

    cin >> Input;

    string Num = "";

    for (int i = 0; i < Input.length(); ++i)
    {
        if (Input[i] == '+' || Input[i] == '-')
        {
            NumberQueue.push(stoi(Num));
            Num = "";
            OperQueue.push(Input[i]);
        }
        else
        {
            Num += Input[i];
        }
    }

    NumberQueue.push(stoi(Num));

    int Result = NumberQueue.front(); NumberQueue.pop();

    while (OperQueue.empty() == false)
    {
        if (OperQueue.front() == '+')
        {
            OperQueue.pop();
            Result += NumberQueue.front(); NumberQueue.pop();
        }
        else
        {
            // sub operator
            OperQueue.pop();
            int Current = NumberQueue.front(); NumberQueue.pop();

            while (OperQueue.empty() == false && OperQueue.front() == '+')
            {
                OperQueue.pop();
                Current += NumberQueue.front(); NumberQueue.pop();
            }

            Result -= Current;
        }
    }

    cout << Result << '\n';
    
    return 0;
}

접근 방식

큐 / 파싱

1. 문자열을 각각 숫자 문자열과 연산자 문자열로 파싱하여 벡터에 삽입
   ex) { “55”, “-“, “50”, “+”, “40” }
2. 해당 백터를 아래와 같이 백트래킹
   1. 벡터를 순회하며 연산자를 발견하면 왼쪽 숫자 , 연산자 , 오른쪽 숫자를 지역 변수에 저장 후 벡터에서 제거
   2. 저장한 변수들로 결과값을 산출한 뒤 다시 벡터에 삽입
   3. 백트래킹
   4. 백트래킹 종료 후 결과값을 벡터에서 제거한 뒤 다시 왼쪽 숫자, 연산자, 오른쪽 숫자를 벡터의 기존 위치에 삽입한다.
3. 시간초과
4. 규칙을 찾아야 했다.
5. ’+’ 연산자가 온다면 결과값에 더한다.
6. ’-‘ 연산자가 오면 그 뒤의 ‘-‘ 연산자 전까지의 모든 값을 더해서 기존의 결과값에서 뺀다.
7. 해결

다시 생각해 볼 점

1. 그리디 알고리즘이었던 이유가 한번 빼기 연산자가 나온다면, 그 뒤의 더하기 연산자를 모두 더해서 가장 큰 값을 만들어서 빼기 때문이라고 생각했다.
2. 이전에 풀었던 문제였는데도, 백트래킹으로 시도했다 시간초과가 뜨고 규칙을 찾는데 시간이 꽤 걸렸다. 우선 문제를 정확하게 분석하는 습관이 필요할 것 같다.