[백준] Greedy: 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

 

문제 접근

주어진 식이 가장 작은 수가 되기 위해서는 -부호 이후부터 다음 -부호까지 괄호로 묶어주면 된다.

즉 "-"를 기준으로 식을 쪼개고 맨 처음 식을 제외한 이후 식을 모두 빼주면 된다.

즉, 0 + 10 - 20 + 30 - 40의 경우  0 +10, 20 + 30, 40 으로 나누고

(0 + 10) - (20 + 30) - (40) 으로 계산하면 된다.

* split이 안될 경우 첫번째 배열에 그대로 들어감.

 

* 근데 왜 Greedy인지 이해가 안된다. 흠..

* 배열을 돌다가 현재 부호가 -이면 무조건 다음 -까지 묶어버려서..?

풀이 코드 

package baekjun;

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


public class _1541 {
//split안되면 그대로 유지됨.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split("-");
        int answer = 0;
        
        String[] plus = split[0].split("\\+");
        
        for (String s : plus) {
            answer += Integer.parseInt(s);
        }

        if (split.length != 1){ // "-" 없는 경우
            answer = getAnswer(split, answer);
        }
        System.out.println(answer);

    }

    private static int getAnswer(String[] split, int answer) {
        for (int i = 1; i < split.length; i++) {
            String[] plus = split[i].split("\\+");

            for (String s : plus) {
                answer -= Integer.parseInt(s);
            }
        }
        return answer;
    }
}