백준 1541 풀이

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

처음 문제를 풀때는 스택을 이용하려고 했다. 하지만 스택으로는 +,-를 구분해서 최소를 구하는게 매우 복잡하고 힘들었다.

그래서 다른 방법을 찾아보려고 했고 최소를 얻기 위해서는 아래와 같은 사실을 이해했다.

1. 더하기는 증가고, 빼기는 감소이다.
2. 최소가 되기 위해서는 작은 수에서 큰 수를 빼는 것이 유리
3. 그렇다면 더하기만 미리 다 더하고 나중에 빼기를 하면 되겠구나

이렇게 이해를 하고 난 다음은 편했다.

입력받은 수식을 우선 "-"로 토큰화하고 이어 "+"로 토큰화하여 덧셈을 먼저해주고 마지막에 뺄셈을 해주는 것으로 답을 구했다.

이때 제일 처음 들어오는 숫자는 양수임에 주의해야한다.

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

public class Main {
    /*static int count = -1;
    static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
    static int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
    static boolean visited[];
    static int n, m;
    static int graph[][];*/

    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String line = br.readLine();
        StringTokenizer stk = new StringTokenizer(line, "-");

        int sum = Integer.MAX_VALUE;
        while(stk.hasMoreTokens()) {
            int tmp = 0;
            StringTokenizer add = new StringTokenizer(stk.nextToken(), "+");

            while(add.hasMoreTokens()){
                tmp = tmp + Integer.parseInt(add.nextToken());
            }

            if(sum == Integer.MAX_VALUE){
                sum = tmp;
            }
            else
                sum -=tmp;
        }

        bw.write(sum+"\n");
        br.close();
        bw.close();
    }

}