[백준] 1542번 - 잃어버린 괄호

 

 

그리디 알고리즘 관련 문제!

접근이 어려워서 다른 분의 풀이를 참고하였다 ....

정리해보려고 한다!

 

 

 

예시 )

1 + 2 - 3 + 4 - 5 + 6 + 7 + 8 - 9 + 10

 

위의 식에서 최소값이 되게 하는 경우는 다음과 같이 괄호를 지정했을 때 이다.

 

1 + 2 - (3 + 4) - (5 + 6 + 7 + 8) - (9 + 10)

 

최소값이 되기 위해서는 "-" 기호 이후에 차감을 하는 숫자가 최대한 커지도록 해야 한다.

따라서 - 이후에는 + 로 연산되는 모든 숫자를 더하고 그 뒤에 빼주는 방식으로 문제를 해결할 수 있다.

 

 

1. 먼저 -를 기준으로 나누어 준다!

2. + 를 기준으로 나누어 더한다.

3. 결과를 list에 저장한다.

4. 리스트의 가장 첫 수는 미리 더해준다.

5. 그 다음 수부터 뺄셈을 한다.

 

 

package 백준.greedy;

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

public class baekjoon_1541 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str= br.readLine().split("-");
        List<Integer> list= new ArrayList<>();
        for (String s : str){
            int sum = 0;
            String[] split= s.split("\\+");
            for (String s1 : split){
                sum+= Integer.parseInt(s1);
            }
            list.add(sum);
        }
        long answer = list.get(0);
        for (int i=1; i<list.size(); i++){
            answer-= list.get(i);
        }
        System.out.println(answer);
    }
}