[백준][C++] 1541 잃어버린 괄호

1541. 잃어버린 괄호

1541번: 잃어버린 괄호

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

처음에는 괄호 문제라 조금 무서웠지만... 조금만 생각하면 쉽게 풀 수 있는 문제였다.

 

inpupt =>
30+20-50+40-30+30

만약, 이런 입력이 있다면, 괄호를 어떻게 묶어야 최솟값이 나올까?

30+20-(50+40)-(30+30)

output =>
-100

무려 원래 답보다 140이나 작은 결과값이 나왔다!

 

알고리즘 설계

1. 마이너스 연산자가 나올 때까지의 모든 수들을 더한다.

 

2. 마이너스 연산자가 나오면 앞으로 나오는 모든 수들을 빼준다.

• 마이너스 연산자가 나오면서부터, 다음 연산자가 어떤 것이든, 앞으로 나올 모든 수들은 마이너스로 묶이기 때문이다.

 

코드

#include <iostream>
using namespace std;

int main()
{
    string formula;
    int num = 0, answer = 0;
    bool isMinus = false;

    cin >> formula;

    for (int i = 0; i < formula.size(); i++)
    {
        if (isdigit(formula[i]))
        {
            num *= 10;
            num += formula[i] - '0';
        }
        else
        {
            // '-'가 한 번도 나온 적 없다면 그냥 연산값 더함
            if (!isMinus)
                answer += num;

            // 나온 적 있다면 괄호로 묶이기 때문에
            // 무엇이든지 빼줌
            else
                answer -= num;

            if (!isMinus && formula[i] == '-')
                isMinus = true;

            num = 0;
        }
    }

    // 마지막 숫자를 마저 더한다
    if (isMinus) num *= -1;
    answer += num;

    cout << answer;
}

간단하게 짜봤다.

 

신선하고 재미있는 문제였다. 해결 방법이 빠르게 생각나서 기분이 좋았다.