[Algorithm] 백준1541_잃어버린 괄호(수학, 문자열, 그리디, 파싱)

1541번: 잃어버린 괄호

문제

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

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

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

 

입력

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

 

출력

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

 

예시 입력 / 출력

input	output
55-50+40	-35

 

풀이 과정

* 입력받은 값을 기준으로 괄호만 사용하여 최소값을 구해야 한다.

-> 입력값의 피연산자 사이에 "+" 연산자가 들어가 있는 경우 해당 피연산자들을 전부 더한 후 첫번째 부터 순서대로 전부 뺴준다. 이해하기 보다 쉽게 아래 예시로 보자!

예시)

0. input -> 30-70-20+40-10+100+30-35

1. 30-70-20+40-10+100+30-35 // "+"연산자의 피연산자들을 괄호로 묶는다.

2. 30-70-(20+40)-(10+100+30)-35 이 된다. // 괄호안의 피연산자 값들을 전부 더한다.

3. 30-70-60-140-35 // 완성된 값들을 앞에서 순서대로 뺀다.

4. 출력 : -275

 

1. "-" 기준으로 split하여 string배열 arr에 담는다.

 

2. 완성된 배열 arr을 반복문으로 요소를 하나씩 꺼낸다.

 

3. 꺼낸 요소의 "+"가 포함되어 있으면 해당 요소를 "+" 기준으로 split하여 새로운 string배열 sTemp에 담는다.

포함되어 있지 않을 경우 요소를 int로 형변환하여 list에 담는다.

 

4. 위의 3번에서 "+"가 포함되어 있을 경우 sTemp배열을 반복문으로 요소를 하나씩 꺼내 숫자일 경우 int로 형변환하여 temp에 누적시킨다.

 

5. 완성된 temp를 list에 담는다.

 

6. list의 첫번째 인덱스의 값은 양수로 시작해서 모든 인덱스를 빼준다.

 

풀이

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String[] arr = s.split("-");

        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if(arr[i].contains("+")){
                int temp = 0;
                String[] sTemp = arr[i].split("\\+");
                for (String x : sTemp){
                    if(!x.equals("+")) temp += Integer.parseInt(x);
                }
                list.add(temp);
            }else{
                list.add(Integer.parseInt(arr[i]));
            }
        }
        int result = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            result -= list.get(i);
        }
        System.out.println(result);
    }
}

---