[백준] 1541번 - 잃어버린 괄호

문제 >

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

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

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

 

입력 >

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

 

출력 >

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

 

해결방법 > 

간단한 수학문제로 -가 나올 때마다 괄호를 처준다. 

만약 32-43-32+11-23+43+13..라는 데이터가 입력되면 32-(43)-(32+11)-(23+43+13)..이런 방식으로 괄호를 쳐준다.

결국 식은 32-43-32-11-23-43-13...이 된다.즉, 음수 부호가 처음 나오는 순간부터 다음 모든 숫자들을 뺄셈하는 식이 된다.

 

[C++]

#include <iostream>
#include <string>
#include <vector>

using namespace std;
// 음수가 나오는 순간부터 모두 빼기
int main(){
    string s;
    string tmp;
    int idx = 0, cnt = 0;
    int flag = 0, sum = 0, num;

    cin >> s;

    for(int i = 0; i < s.size(); i++){
        if(s[i] == '+' || s[i] == '-'){
            // 문자열 슬라이싱
            tmp = s.substr(idx, cnt); // 이전 부호부터 다음 부호까지의 값 저장
            idx = i+1; // 다음 부호 인덱스
            cnt = 0; // 숫자 카운트
            num = stoi(tmp);
            
            // 플래그 값에 따라 숫자를 더할지 뺄지 결정
            if(flag == 1)
                sum -= num;
            else
                sum += num;
            
            // 빼기가 시작되면 플래그 on
            if(s[i] == '-')
                flag = 1;
        }
        else{
            cnt++;
        }
    }
    //마지막 숫자
    tmp = s.substr(idx, cnt);
    num = stoi(tmp);
    if(flag == 1)
        sum -= num;
    else{
        sum += num;
    }
    cout<< sum;
}

 

[JAVA]

package baekjoon;

import java.util.*;

public class BOJ_1541 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String[] a = s.split("-");
		int sum = 0;
	
		for(int i = 0; i < a.length; i++) {
			String[] tmp = a[i].split("\\+");
			for(int j = 0; j < tmp.length; j++) {
				if(i == 0 && s.charAt(0) != '-')
					sum += Integer.parseInt(tmp[j]);
				else
					sum -= Integer.parseInt(tmp[j]);
			}
		}
		
		System.out.println(sum);
	}
}

 

문제링크 >

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

1541번: 잃어버린 괄호