그리디: 잃어버린 괄호 (백준 1541)

○ 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 128 MB 65126 34393 27106 52.229%

○ 문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

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

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

○ 입력 예제
55-50+40

○ 출력 예제
-35

---

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int sum = 0;
		String[] subtraction = sc.nextLine().split("-");
		/* 1. input: 55-50+40
		   2. split("-"): [55, 50+40] */
		
		for (int i = 0; i < subtraction.length; i++) {
			int temp = 0;
			
			//뺄셈으로 분리된 토큰을 덧셈으로 다시 분리
			String[] addition = subtraction[i].split("\\+");
			/* 1. i == 0: [55] => [55]
			   2. i == 1: [50+40] => [50, 40] */
			
			//덧셈으로 나눈 토큰 모두 더함
			for (int j = 0; j < addition.length; j++) {
				temp += Integer.parseInt(addition[j]);
			}
			/* 1. i == 0 temp: 55
			   2. i == 1 temp: 90 */
			   
			//첫번째 토큰인 경우 temp 값이 첫 수
			if (i == 0) {
				sum = temp;
			} else {
				sum -= temp;
			}
			
		}
		
		System.out.println(sum);
		
	}
	
}

○ 확인
- Scanner.next()의 경우 Space 및 Enter를 구분자로 인식하여 저장되지 않음.
- 최소값이 되기 위해서는 -기호 이후에 차감을 하는 숫자가 최대한 커지도록 해야 한다.
- mapToInt 메서드: 스트림을 IntStream으로 변환해주는 메서드

import java.util.stream.Stream;

int[] calAry = Stream.of(cal.replaceAll("[^0-50]", "_").split("_")).mapToInt(Integer::parseInt).toArray();