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

문제

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

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

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

입력

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

출력

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

 

package algorithm;

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

public class 잃어버린괄호_1541 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		String str = sc.nextLine();
		ArrayList<Character> lstVal = new ArrayList<>();
		
		// 기호를 담는 배열
		for(int i = 0; i < str.length(); i++) {
			if(str.charAt(i) == '-' || str.charAt(i) == '+') {
				lstVal.add(str.charAt(i));
			}
		}
		// '-'이거나 '+'일때 문자열 자르기 (숫자를 담는 배열
		String[] arr = str.split("-|\\+");
		
		// 배열 맨 처음 숫자값
		int hap = Integer.parseInt(arr[0]);
		boolean flag = true;
		for(int i = 1; i < arr.length; i++) {
			int num = Integer.parseInt(arr[i]); // 정수형으로 변환하여 합
			if(lstVal.get(i-1) == '-') flag = false;
			// 문자 배열에 마이너스가 있는 이후는 전부 뺄셈
			if(flag) {
				hap += num;
			} else {
				hap -= num;
			}
		}
		
		// output
		System.out.println(hap);
	}

}

 

처음 문제를 봤을 때 당황했던 점은 괄호를 넣어주라는 문장 때문이었다. 하지만 괄호를 넣어주라는 것은 단순히 계산의 순서를 적절히 조정하라는 말일뿐 실제로 괄호를 넣어줄 필요는 없다는 것을 깨달았다..

 

10+30-40+60+30-60-70+50 이라는 문장이 있다 했을 때 우리는 이 계산식의 최소값을 구하기 위해 적절히 계산의 순서를 정해주어야한다.

 

이 계산식을 보던중에 떠오른 생각은 맨 처음 등장하는 마이너스(-) 이후에 등장하는 숫자들은 전부 빼주도록 할 수 있다는 것이었다.

위 식을 예로

 

10+30-(40+60+30)-60-(70+50) 이 최소값을 구하는 식이 되는데 이는 결국

10+30-40-60-30-60-70-50 이라는 식이 될 수 있다.

 

그래서 숫자를 담은 배열과 각 문자를 담은 리스트 두개를 생성하여 문자 리스트중 마이너스(-)가 등장한 인덱스 뒤의 숫자들을 전부 빼주어서 문제를 해결하였다.

 

분배법칙을 이해한다면 훨씬 쉽게 접근할 수 있었던 문제라고 생각한다.