백준 1541번 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

 

출력

첫째 줄에 정답을 출력한다.

 

풀이

입력의 모든 문자는 '0'~'9', '+', '-' 이기 때문에 'x', '%' 처럼 연산 순서를 크게 신경 쓰지 않아도 된다.

단, 괄호를 이용해 식의 값을 최소로 바꾸기 위해서 필요한건 하나뿐인데 '-'가 앞에 있을 때 바로 뒤에 '+' 연산이 나오면 괄호를 쳐서 -로 바꿀 수 있다는 점이다.

예를 들어 -10+20+30-10 은 -(10+20+30)-10 = -70이 된다.

이것보다 어려운 건 이 문제의 입력을 어떻게 받느냐인데,

우선 길이가 최대 50이므로 크기 50짜리 문자열을 만들어 입력받고,

이후 "숫자"와 "연산자"를 따로 담을 vector를 만든다. 숫자는 5자리 이하이기 때문에 "연산자"가 나올 때까지 10씩 곱해서 정수화시키고, "연산자"가 나오면 즉시 여태 만든 정수를 이미 만들어 둔 vector에 담는다. 이를 반복하면 입력 문제를 해결할 수 있다.

 

소스 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
    string s; cin >> s;
    vector<int> v1; //수를 담을 벡터
    vector<int> v2; //부호를 담을 벡터 1/-1
    int temp = 0; int ans = 0;
    v2.push_back(1);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '+' || s[i] == '-') {
            if (s[i] == '+') v2.push_back(1);
            else if (s[i] == '-') v2.push_back(-1);
            v1.push_back(temp);
            temp = 0;
        }
            else {
                temp = temp * 10 + (s[i] - '0');
            }
    }
    v1.push_back(temp);
    int cur_sign = 1; //현재 부호
    for (int i = 0; i < v1.size(); i++) {
        if (v2[i] == 1) { //마주친 부호가 양수
            if (cur_sign == -1) { //그 전에 음수였을 때
                ans -= v1[i];
                cur_sign = -1;
            }
            else ans += v1[i];
        }
        else {  // '-' 부호일 때
            if (cur_sign == -1) ans -= v1[i];
            else {
                cur_sign = -1;
                ans -= v1[i];
            }
        }
    }
    printf("%d", ans);
    return 0;
}

추가 설명

 

 
    int cur_sign = 1; //현재 부호
    for (int i = 0; i < v1.size(); i++) {
        if (v2[i] == 1) { //마주친 부호가 양수
            if (cur_sign == -1) { //그 전에 음수였을 때
                ans -= v1[i];
                cur_sign = -1;
            }
            else ans += v1[i];
        }
        else {  // '-' 부호일 때
            if (cur_sign == -1) ans -= v1[i];
            else {
                cur_sign = -1;
                ans -= v1[i];
            }
        }

이 부분에서 헷갈릴 수 있으나, 단순하게 -로 바꿔주는 과정이라고 생각하면 편하다.

-가 한 번 나오기 시작하면 다음 -가 나올 때까지 모든 +를 뒤집어주는데, 이렇게 반복되면 마지막까지 모든 +는 뒤집힌다.(다음 -를 또 찾았거나 못 찾았어도 쭉 뒤집히기 때문)

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~