백준 1541번 - 잃어버린 괄호

문제

백준 1541번 - 잃어버린 괄호

아이디어

• 최소로 만들기 위해서는 최대한 큰 수를 빼야한다.
• 식을 빼기(-)로 구분하면 자연스럽게 더하기(+)만 있는 식에 괄호를 치는 효과를 볼 수 있다.
• 구분된 식들을 다시 더하기로 구분해서 모두 더해주고, 차례대로 뺄셈을 해주면 된다.
• 대신 첫 번째 식은 덧셈을 해주어야 한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N)

코드 구현

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

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

        String[] s = br.readLine().split("-");

        boolean first = true;

        int ans = 0;

        for (String str : s) {

            int sum = getSum(str);

            if (first) {
                first = false;
                ans += sum;
            } else {
                ans -= sum;
            }
        }

        System.out.println(ans);
    }

    private static int getSum(String str) {

        String[] split = str.split("\\+"); //escape

        int sum = 0;

        for (String s : split) {
            sum += Integer.parseInt(s);
        }

        return sum;
    }
}