[백준/Java] 1541

잃어버린 괄호

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

문제

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

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

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

입력

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

출력

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

문제 풀이 방법 및 해설

이번 문제는 그리드 알고리즘이다. 주어진 식을 괄호를 적절히 쳐서 최소값으로 바꾸어 주어야 한다. 최소값으로 만드는 명제는 -뒤에 값을 크게 하는 것이다. 즉 '-' 뒤에 '+' 하는 값을 괄호로 묶어주는 것을 의미한다.

만약 '-' 뒤에 '+' 하는 값을 괄호로 묶지 않은 것이 더 크다며 위 명제는 틀린 것이다. 하지만 '-' 뒤에 '+' 하는 값을 묶지 않으면 그 값은 +로 남기 때문에 명제가 맞다고 할 수 있다.

실제 풀이는 '-'를 기준으로 문자열을 끊어준다. 그리고 끊은 문자열을 전부 다시 '+' 기준으로 분리하고 계산한 값을 리스트에 저장한다.

그렇다면 리스트에 있는 값을 전부 빼주면 되는데 주의할 점은 제일 첫 번째 값은 +으로 해주어야한다. 이유는 가장 처음에 등장하는 숫자는 +이기 때문이다.

예시로 55-50+40이 있으면 '-'로 끊은 55, 50+40으로 나눠지고 이를 다시 '+'기준으로 나눈 값을 더하고 리스트에 추가하게 되면 리스트에는 55, 90이 들어간다.

첫 번째 값은 +55로 들어가고 이후부터는 모두 빼면 값은 -35가 된다.

풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        String[] split = str.split("-");
        ArrayList<Integer> arr = new ArrayList<>();

        for(int i = 0 ; i < split.length ; i++){
            String[] s = split[i].split("\\+");
            int sum = 0;
            for(int j = 0; j < s.length ; j++){
                sum += Integer.parseInt(s[j]);
            }
            arr.add(sum);
        }

        int answer = arr.get(0);
        for(int i = 1 ; i < arr.size(); i++){
            answer -= arr.get(i);
        }

        System.out.println(answer);
    }
}