[백준/Java] 1541 : 잃어버린 괄호

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

 

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

 

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

 

실제 풀이는 '-'를 기준으로 문자열을 끊어줍니다. 그리고 끊은 문자열을 전부 다시 '+' 기준으로 분리하고 계산한 값을 리스트에 저장합니다. 그렇다면 리스트에 있는 값을 전부 빼주면 되는데 주의할 점은 제일 첫 번째 값은 +으로 해주어야합니다. 왜냐하면 가장 처음에 등장하는 숫자는 항상 +이기 때문입니다.

 

예시로 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 Backjoon_1541_잃어버린_괄호 {
    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);
    }
}