[알고리즘] 백준 1541 잃어버린 괄호 - JAVA

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

그리디 보다는 문자열 파싱하는게 주된 문제인 것 같다.

 

풀이과정을 요약하자면, 55-50+40 이라는 문자열에 임의로 괄호를 씌워 최소값을 만드는 문제이다. -> 55-(50+40)

 

최소값을 구하기 위해서는 '큰 숫자를 빼야한다' 즉 덧셈에 괄호를 씌워 먼저 계산하여 큰 수를 만들어 빼는 것이다.

 

이를 위해서 '-'로 토큰을 만든 다음 그 토큰 안에서 '+'를 통해 또 토큰을 나눈다.

 

소스코드

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

public class Main {

    static int result = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, "-");

        while (st.hasMoreTokens()) {
            s = st.nextToken();

            int sum = 0;
            StringTokenizer st2 = new StringTokenizer(s, "+");

            while (st2.hasMoreTokens()) {
                sum += Integer.parseInt(st2.nextToken());
            }

            if (result == Integer.MIN_VALUE) { // result가 Integer.MIN_VALUE라면 맨 첫번째 항으로 생각
                result = sum; // 첫째항이므로 그냥 넣어준다.
            }
            else {
                result -= sum;
            }
        }


        System.out.println(result);
    }
}