백준 1541번 잃어버린 괄호

잃어버린 괄호는 주어진 식에 괄호를 대입하여 식의 값을 최소로 만드는 문제다.

 

55-50+40 의 값을 최소로 만들기 위해서는 괄호를 어디에 배치해야 할까? 덧셈과 뺄셈을 사용해 식을 계산할 때 최소값을 얻기 위해서는 되도록 큰 수를, 그리고 여러번 빼줘야한다.

 

따라서, (-)를 기준으로 양 옆을 각각 괄호로 감싼다면 최소값인 -35 를 얻을 수 있다.

 

만약 1+2 - 3+4 - 5+6 이라는 식이 주어진다면 어떨까? 이 역시 마찬가지로 (-)를 기준하여 식을 괄호로 감싸면 최소값을 얻을 수 있다.

 

1+2 - 3+4 - 5+6 ---> (1+2) - (3+4) - (5+6)

 

이를 코드로 구현하기 위해서 아래와 같은 순서로 진행하였다.

1. 주어진 식을 ( - )를 기준으로 나눈다.
   "55-50+40" ---> ["55", "50+40"]
2. 분리된 식의 각 조각을 계산한다. 
   ["55", "50+40"] ---> [55, 90]
3. 2에서 얻은 첫 번째 값에서 나머지 값을 모두 빼준다.
   55 - 90 = -35

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        String fullEqn = in.next(); // [55-50+40]

        int ans = 0;

        // 1. - 를 기준으로 식 분리 [55, 50+40]
        String[] partEqn = fullEqn.split("-");

        for (int i = 0; i < partEqn.length; i++) {
            String eqn = partEqn[i]; // [55], [50+40]

            int partSum = 0; // 분리된 식 덩어리 1개의 계산 값을 담을 변수

            // + 를 기준으로 식 분리
            String[] nums = eqn.split("\\+"); // [55] => [55], [50+40] => [50, 40]

            for (int j = 0; j < nums.length; j++) {
            	// 2. 각 숫자를 모두 더함 [55], [90]
                partSum += Integer.parseInt(nums[j]); 
            }

            // 3. 첫 번째 식 덩어리의 계산 값을 기준으로 나머지를 뺀다
            if (i == 0) {
                ans = partSum; // partSum = [55]
            } else {
                ans -= partSum; // partSum = [90]
            }
        }
        System.out.println(ans);
    }
}