[JAVA] 백준 1541 - 잃어버린 괄호

 

실버 II

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

1541번: 잃어버린 괄호

---

📌 문제

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

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

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

---

📤 입력

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

---

📥 출력

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

---

💡 접근방식

이 문제의 핵심은 '+'부터 계산을 하는 것이다. 

따라서 처음에는 '-'를 기준으로 잘라주었고 그 다음 '+'를 기준으로 잘라 '+'를 계산해주고 나머지를 빼주어 제일 작은 수를 출력할 수 있도록 하였다.

 

아래의 입력을 예시로 설명해보자면 처음에는 '-'를 기준으로 자르므로 splitMinus배열에 다음과 같이 저장된다.

55-50+40

splitMinus[0] = 55

splitMinus[1] = 50 + 40

 

그 다음 반복문으로 들어가게 되고, splitMinus[] 문자열을 '+'를 기준으로 잘라준다.

splitMinus[0]은 +가 없으므로 그대로 add에 55가 저장되고, 55가 맨 처음 값이므로 result의 초기값으로 설정된다.

맨 마지막은 add를 초기화해준다.

splistMinus[1]은 +가 있으므로 splitPlus[0] = 50, splistPlus[1] = 40과 같이 저장된다.

그리고 두 값은 add에 더해져 저장되므로 add = 90이 된다.

이 둘은 맨 처음 값이 아니므로 result에서 빼준다.

따라서 최종적으로 -35가 출력된다.

---

💻 코드

package Greedy;

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

public class SLIVER2_BJ1541 {
    /*https://www.acmicpc.net/problem/1541
        잃어버린 괄호
     */
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int add = 0;
        int result = 0;
        //식 입력
        String formula = br.readLine();

        //마이너스를 기준으로 자르기
        String[] splitMinus = formula.split("-");

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

            //플러스 기준으로 자르기
            String[] splitPlus = splitMinus[i].split("\\+");

            //플러스로 자른 값들 더하기
            for(int j = 0; j < splitPlus.length; j++)
                add += Integer.parseInt(splitPlus[j]);

            //맨 앞에 있는 수를 result의 초기값으로 설정
            if(i == 0)
                result = add;
            
            //그 외에는 다 빼주기
            else{
                result -= add;
            }
            
            //add초기화
            add = 0;
        }

        //결과 출력
        System.out.println(result);

    }
}

---

📝 NOTE

split을 이용하는 방법을 모르면 접근하기 힘든 문제이다.

다른 사람들의 풀이를 찾아보다가 아래 블로그에 그림이랑 같이 설명이 잘 나와있어 참고하면 좋을 것 같다.

https://st-lab.tistory.com/148

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