[백준] 그리디알고리즘 - 1541번 잃어버린 괄호 java 자바

문제

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

1541번: 잃어버린 괄호

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

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

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

 

풀이

최소를 만들기 위해선 최대한 큰 수를 빼주어야 한다. 이를 위해선 -를 기준으로 식을 나누어 그 사이의 수식에 대해 덧셈 계산을 한 후에 빼준다. 예제를 보면 55-(50+40)으로 묶었을 때 최솟값인 -35가 나온다. 

이를 위해 먼저 수식을 -를 기준으로 나누어야 하는데 split 또는 StringTokenizer를 이용하여 나눌 수 있다. 사실 나는 원래는 반복문과 charAt을 사용하여 한글자씩 쪼개주는 걸 선호하는데(걍 편해서..) 이 문제는 split이나 StringTokenizer를 사용하는 것이 훨씬 간편해서 split을 이용하여 풀었다.

-를 기준으로 식을 나누었으면 +를 기준으로 다시 식을 나누어 숫자들끼리 덧셈을 수행한다.

 

 코드

package 그리디알고리즘;

import java.util.Scanner;
public class No1541_잃어버린괄호 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int sum=Integer.MAX_VALUE;
		String [] splitArr=sc.next().split("-");
		
		for(int i=0;i<splitArr.length;i++) {
			int temp=0;
			// \\+ 인 이유 : +가 메타문자이기때문에 이스케이프처리를 해야하는데
			// 백슬래시도 단독으로 출력할 수 없기 때문에 \\+
			String[] add=splitArr[i].split("\\+");
			
			for(int j=0;j<add.length;j++)
				temp+=Integer.parseInt(add[j]);
			
			//가장 처음 수인 경우 항상 양수이기 때문에 sum이 초기값이라면 temp값 그대
			if(sum==Integer.MAX_VALUE)
				sum=temp;
			else
				sum-=temp;
		}
		
		System.out.println(sum);
	}

}