[백준 1541] 잃어버린 괄호

잃어버린 괄호

문제설명

첫 줄에 수식을 입력받고 괄호를 마음대로 배치해서 최대한 작은 값을 만들어 출력한다.

---

알고리즘

1. 수식을 입력 받는다.
2. 뺄셈 부호를 만나면 체크 할 수 있도록 확인하는 bool형 변수와 숫자를 담을 수 있는 변수를 만든다.
3. 수식을 각각 읽으면서 부호를 만나거나, 문장의 끝부분을 만나면 sum이라는 결과를 저장하는 변수에 연산을 진행한다.
4. 문자열 처리중에 -를 만나면 bool형 변수를 true로 변경시킨다
5. 반복문 내에서 부호나 문장의 끝부분을 만나지 않은 경우에는 string형 temp 변수에 저장한다
6. bool형 변수가 true인 경우 모두 뺄셈을 진행하고 그렇지 않은 경우 덧셈을 진행한다
7. 결과 값을 출력한다.

---

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
using namespace std;

int main(void)
{
    string s;
    cin >> s;

    int sum = 0;
    string temp;
    bool minus = false;//음수 체크
    for (int i = 0; i <= s.length(); i++)
    {        
        if (s[i] == '+'||  s[i]=='-' || s[i]=='\0')//부호를 만나는 경우 or 마지막 숫자를 계산하기 위한 경우
        {
            if (minus)//음수이면 계속 뺀다
                sum -= stoi(temp);
            else//음수가 아니면 더한다
                sum += stoi(temp);

            if (s[i] == '-')//음수를 만나면 check
                minus = true;
            temp = "";//숫자 사용후 초기화
        }
        else
            temp += s[i];//숫자 저장
    }
    cout << sum << "\n";//결과 출력
    return 0;
}

고찰

문제를 생각해보면 마이너스를 만난 순간 부터 다 뺄셈으로 연산된다고 생각하면된다.
그 이유는 최소한으로 값을 만들어야하기 때문에 -이후에 +가 나와도 괄호로 처리해야 가장 작은 값으로 만들 수 있기 때문이다.

문제의 예시외의 경우도 마찬가지다.

---

• ex1 혼합 된 경우) 45-50-20+70-20 의 수식이 들어왔다고 가정하자.
  45-(50)-(20+70)-20으로 처리하면 가장 작은 값이 나오는 것을 알 수 있다.
  이러한 경우는 첫 45는 덧셈이고 그 뒤의 뺄셈이 나온 순간부터 전부 뺄셈으로 처리되는 것을 알 수 있다.
• ex2 전부 덧셈인 경우) 50+20+10과 같이 모두 덧셈으로 연결된 경우 위의 작성한 코드에서 뺄셈을 만나지 않으니 모두 덧셈만 이루어진다.
• ex3 전부 뺄셈인 경우) 20-10-15와 같은 경우는 첫 수를 제외하고 모두 뺄셈이므로 bool type변수가 모두 뺄셈이 되도록 처리한다. 이때 처음 들어온 수와 마지막으로 들어온 수는 부호를 갖고 있지 않는다. 따라서 위와 같은 방식으로도 처리할 수 있다.