[백준] 1541. 잃어버린 괄호

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

1541번: 잃어버린 괄호

문제 해결법을 떠올리는 건 쉽다. 연산의 최소 값을 구해야 하므로 -가 붙는 수를 최대한 크게 만들면 된다.

 

예를 들어 다음과 같이 식이 있다고 가정하자.

a + b - c + d + e -f

그러면 -의 값을 최대한 크게 만들기 위해 c, d, e를 한 묶음으로 묶어주면 된다.

 

문제는 값이 입력될 때 숫자와 연산자를 어떻게 구분하고 어떻게 저장할지 고민이었는데..

-를 기준으로 먼저 나눈 후, 각 덩어리들의 합을 구하고 그들 간에 - 연산을 해주면 된다.

 

즉 위 예제에서 (a + b), (c + d + e), f 이렇게 총 3개의 덩어리가 나온다. 그리고 (첫 번째 덩어리) - (두 번째 덩어리 값) - (세 번째 덩어리 값)이 답이 된다!

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

import java.io.InputStreamReader;
import java.util.*;

// 시간복잡도: O(N)
public class Main {

    static int answer = 0; // 연산의 최소값
    static List<Integer> numbers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), "-");
        while (st.hasMoreTokens()) {
            numbers.add(getSum(st.nextToken()));
        }

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

        System.out.println(answer);
    }

    private static Integer getSum(String str) {
        int sum = 0;
        String[] arr = str.split("\\+");
        for (String s : arr) {
            sum += Integer.parseInt(s);
        }
        return sum;
    }
}