[백준] JAVA 자바 : 잃어버린 괄호 (1541번)

.

---

괄호를 적절히 넣어서 가장 최소값이 만들어지는 식을 만들면 된다.
얼핏 보면 꽤 복잡해 보여서 상당히 시간을 썼는데... 조금만 생각해 보니, 굉장히 간단했다.

 

식에서 '-' (빼기 기호)를 만나기 전까지는 모든 수를 다 더해주고,
'-'를 만난 이후부터는 모든 수를 다 빼주면 된다!

왜냐고?? 빼기가 포함된 값들은 모두 괄호를 쳐서 빼주면 최소값이 나올 거니까!
1 + 2 - 3 + 4 - 5 여기서, 가장 최소값은 1 + 2 - (3 + 4) - (5) 이런 식으로 만들어질 수 있는 것!!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.StringBuilder;

public class MissingBracket {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        boolean bool = false;
        String expr = br.readLine();

        int sum = 0;
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<expr.length(); i++) {
            char ch = expr.charAt(i);

            if (bool == false) { // -를 만나지 않았을 경우는 모두 더함
                if (ch == '-') {
                    sum += Integer.parseInt(sb.toString());
                    sb = new StringBuilder();
                    bool = true;
                } else if (ch == '+') {
                    sum += Integer.parseInt(sb.toString());
                    sb = new StringBuilder();
                } else {
                    sb.append(ch);
                }
            } else { // -를 만난 이후부터는 모두 뺀다
                if (ch == '+' || ch == '-') {
                    sum -= Integer.parseInt(sb.toString());
                    sb = new StringBuilder();
                } else {
                    sb.append(ch);
                }
            }
        }

        if (bool == false) {
            sum += Integer.parseInt(sb.toString());
        } else {
            sum -= Integer.parseInt(sb.toString());
        }

        System.out.println(sum);
    }
}

ㅋㅋㅋ 근데 어찌 저찌 풀긴 했는데...
이건 그리디 알고리즘을 써서 푼 건 아닌 것 같기도...? ㅋㅋㅋ

 

로그인