잃어버린 괄호

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // eg. 55 - 50 + 40

        // '-' 기준으로 나눠서 담음
        //[55, 50 + 40]
        String[] numbers = br.readLine().split("-");

        for(int i=0; i<numbers.length; i++){
            if(numbers[i].contains("+")){
                int sum = 0;
                // + 가 있으면 묶어서 더해줌 (괄호 연산)
                String[] addNum = numbers[i].split("\\+");
                // [55, [50,40]]
                for(String addnum : addNum){
                    sum += Integer.parseInt(addnum);
                }
                // [55, 90]
                numbers[i] = Integer.toString(sum);
            }
        }

        int min = Integer.parseInt(numbers[0]);
        for(int i=1; i< numbers.length; i++){
            min -= Integer.parseInt(numbers[i]);
        }

        System.out.println(min);

    }
}

해결 로직은 간결하나 문자열을 파싱하는 것이 까다로웠던 문제..
최솟값을 만드는게 목표이므로 최대한 숫자를 +로 묶는다.
연산식 자체가 문자열로 주어지므로 어떻게 파싱할 것인가가 관건이다.
- 1번째로 "-"를 구분자로 분리하여 String 배열(numbers)에 담아준다.
- " 55-50+40" -> [55, 50+40]
- "-" 구분자로 분리하여 담은 numbers를 순회하면서 "+"를 포함한 원소가 있다면 모두 더해주는 연산을 수행한다.
- "+"를 포함한 원소를 numbers[i]라고 가정했을 때, 다시 numbers[i]를 "+"를 구분자로 분리하여 String 배열에 담아준다.(addSum)
- [55, 50+40] -> [55,[50,40]]
- addSum을 순회하면서 숫자를 모두 더해준다. 그리고 더해준 최종값을 numbers[i] 자리에 update해준다.
- 그렇게 되면 최종적으로 [55,90] 이런식으로 담기게된다.
- 차례대로 순회하면서 빼주면 된다.
- 55 -90 = -35