[백준1541번] 잃어버린 괄호

문제

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

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

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

입력

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

출력

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

예제 입력 1

55-50+40

예제 출력 1

-35

 

나의 풀이

-가 나오면 여는 괄호를 붙이고 다음 -가 나오면 괄호를 닫으면 더해진 결과도 결국 음수로 바뀌게 된다. 보기쉽게 말하면
5-4+6-4-7이 있으면 5-(4+6)-(4)-(7)로 바꾸면 최솟값이 된다는 것이다.

문제를 이렇게 풀면 되겠구나는 금방 알아챘지만 나는 저기에 실제로 괄호를 집어넣고 그걸 계산하는 방법으로 문제를 풀려고 문자열을 수식으로 변환하는 여러 방법에 대하여 검색을 해보았지만 찾지못하였다. 그래서 문제에 대하여 해답을 찾아보고 아래 첨부하는 블로그에서 도움을 받아 풀었다.

알아낸 방법은 일단 문자열을 split을 사용해서 -를 기준으로 나누어 배열에 저장한 뒤 각각의 숫자를 모두 뺄셈연산을 하되 중간중간 +가 포함된 원소를 함수를 만들어 덧셈연산한 결과를 가지고 뺄셈을 하게했다. 아래 코드를 보면 쉽게 이해를 할 수 있을 것이다.

• 참고 : https://plplim.tistory.com/30

 

코드

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

/**
 * 1541번 일어버린 괄호
 */
public class Baeckjun1541 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] exp = br.readLine().split("\\-");

        int result = 0;
        for (int i=0; i<exp.length; i++) {
            int num = plus(exp[i]);

            if (i==0) result = num;        // 처음 숫자는 빼면 안된다.
            else result -= num;
        }

        System.out.println(result);
    }

    private static int plus(String str) {
        String[] expPlus = str.split("\\+");
        int result = 0;

        for (String num : expPlus) {
            result += Integer.parseInt(num);
        }
        return result;
    }
}