[java] 백준 1541번 문제(잃어버린 괄호)

원본 링크 : https://www.acmicpc.net/problem/1541

---

문제설명

 

 

소스코드

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

public class Boj_1541
{
    /*
        10+20-30+40-50+60 = 10+20-(30+40)-(50+60)
        = 10+20-(30+40+50+60)
     */
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int sum = Integer.MAX_VALUE; // 첫 번째 토큰 체크용으로 MAX_VALUE로 초기화
        StringTokenizer minus = new StringTokenizer(br.readLine(), "-"); // '-'기준으로 토큰을 나눔

        while (minus.hasMoreTokens()) // 다음 토큰이 존재한다면
        {
            int temp = 0;
            StringTokenizer plus = new StringTokenizer(minus.nextToken(), "+"); // '-'으로 나뉜 토큰을 다시 '+'으로 분리

            while (plus.hasMoreTokens()) temp += Integer.parseInt(plus.nextToken()); // 해당 토큰들을 모두 더함
            if (sum == Integer.MAX_VALUE) sum = temp; // 첫 번째 토큰인 경우 더함
            else sum -= temp; // 첫 번째 토큰이 아닐경우 모두 뺌
        }
        System.out.print(sum);
    }
}

 

설명

• 가능한 한 큰 수를 빼는 것이 최소값을 만드는 방법임
• 따라서 - 기호를 기준으로 식을 나누고, 각 부분에서 + 연산을 먼저 수행한다.
• 첫 번째 그룹은 더하고, 나머지 그룹들은 모두 빼준다.

예를 들어
10 + 20 - 30 + 40 - 50 + 60 이렇게 주어졌다면 - 를 기준으로 토큰을 분리하면 아래와 같이 3개의 토큰으로 나뉘어진다.
10 + 20
30 + 40
50 + 60

10 + 20 = 30이고, 첫 번째 토큰이므로 더해서 sum은 30이 된다.
30 + 40 = 70이고, 첫 번째 토큰이 아니므로 빼서 sum은 -40이 된다.
50 + 60 = 110이고, 첫 번째 토큰이 아니므로 빼서 sum은 -150이 된다.

10 + 20 - 30 + 40 - 50 + 60 -> 10 + 20 - (30 + 40) - (50 + 60) = 10 + 20 - (30 + 40 + 50 + 60)