[백준] 자바 Java, 1541번: 그리디 알고리즘 > 잃어버린 괄호

1541번: 잃어버린 괄호

---

문제

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

그리고 나서 세준이는 괄호를 모두 지웠다.

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

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

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.

그리고 연속해서 두 개 이상의 연산자가 나타나지 않고,

5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

입력으로 주어지는 식의 길이는 50보다 작거나 같다.

 

출력

첫째 줄에 정답을 출력한다.

 

 

알고리즘 분류

• 수학
• 문자열
• 그리디 알고리즘
• 파싱

 

나의 풀이

1. "-" 연산자 제거

2. "+" 연산자와 남아있는 숫자끼리 더하기

3. 첫 번째 수의 경우 더해주고, 나머지 값들은 빼주기

package baekjoon.level16_greedyAlgorithm;

import java.io.IOException;
import java.util.Scanner;

//백준 1541번 문제] 잃어버린 괄호
public class Baekjoon1541 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String[] arr = sc.nextLine().split("-");

        int result = Integer.MAX_VALUE; //Integer.MAX_VALUE로 줘야 함!

        for(int i=0; i<arr.length; i++) {
            int temp = 0;

            //"-"으로 나뉜 토큰을 "+"로 나누거나 +가 포함되지 않을 경우 현재 값 그대로 가져옴
            String[] plusArr = arr[i].split("\\+");

            for(String s : plusArr) {
                temp += Integer.parseInt(s);
            }

            if(result == Integer.MAX_VALUE) { //첫번째 수가 들어오는 경우
                result = temp;
            } else {
                result -= temp;
            }
        }

        System.out.println(result);
    }
}

 

• 참고

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

 

결과