[백준] 1541 : 잃어버린 괄호 (초기값 확인하는 방법에 대해) - JAVA

백준 알고리즘 분류 (그리디 알고리즘) 

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

1541번: 잃어버린 괄호

 

 

 

# 문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

# 예제

입력 : 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

55-50+40

 

출력

-35

 

# 필요개념

주어진 식으로 최솟값을 만들어내려면, -와 - 사이의 식을 먼저 계산해야한다. 예를들어 

20 + 30 - 60 + 30 + 10 - 20 + 30 이 있다면, -뒤에있는 60 + 30 + 10 과 20 + 30 을 먼저 계산하여 20 + 30 - ( 60 + 30 + 10 ) - (20 + 30) 이런 모양의 식을 풀어내야 한다. 바꿔말하면 덧셈연산을 먼저 해야한다는 의미이다!

 

 ✅덧셈 연산을 먼저 하려면

덧셈 먼저 연산을 하기 위해서는 뺄셈 연산을 기준으로 문자열을 나누어야 한다. 위 예시 식을 뺄셈 연산을 기준으로 나눠주면 (20 + 30), (60 + 30 + 10), (20 + 30) 이렇게 나누어진다. 나누어 진 것을 +를 기준으로 쪼개어 더해주면 구할 수 있다.

 

문자열을 쪼갤 때는 크게 두가지 방법을 쓸 수 있다.

• String의 split() 메소드
• StringTokenizer

필자는 StringTokenizer을 이용했다. StringTokenizer에 대한 자세한 설명을 아래 링크에 기록해두었다.

https://wanna-developer02.tistory.com/71

[백준] 2501 : 약수 구하기 (StringTokenizer 활용하기) - JAVA

 

그런데 뺄셈 기준으로 나눈 StringTokenizer중 모두 빼기 연산을 시키면 안된다. 첫 수는 양수이기 때문에 이 부분을 주의해줘야 하는데, 첫 토큰을 구별하는 방법에 대해 고민해보았다. 구글링을 해보니 첫 수를 특수한 수 (Integer.MAX_VALUE나 Integer.MIN_VALUE) 로 지정해두고, 값이 같으면 변화하지 않은 것이므로 첫번째토큰이라고 생각하는 것이다. 난 항상 for문을 사용해 i == 0 을 기준으로 했는데 이렇게 하면 while문을 활용할 때 불편했었다. 이런 방법도 있음을 알게 된 문제였다!

 

# Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer ab = new StringTokenizer(br.readLine(), "-");
        int total = Integer.MIN_VALUE;

        while (ab.hasMoreTokens()) {
            int sum = 0;
            StringTokenizer ad = new StringTokenizer(ab.nextToken(), "+");

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

            if (total == Integer.MIN_VALUE) total = sum;
            else total -= sum;
        }
        System.out.println(total);
    }
}

 

# 결과