[Java] 백준 1541번: 잃어버린 괄호

[문제 바로 가기] - 잃어버린 괄호

💡 접근 방식

최적해를 찾는 그리디로 접근하면 되는 문제로 결국 최솟값을 찾아야 하므로 빼는 부분이 가장 최대가 되어야 한다. 예시와 같이 55-50+40일 땐 빼는 부분이 최대인 55-(50+40)가 되어야 한다는 뜻이다.

따라서 1. -를 기준으로 수식 나누기 2. 나눈 수식의 값 가장 더해서 sum에서 빼기 (단, 가장 첫번째 수는 항상 양수이므로 제외해야 함)

-와 +를 기준으로 나눌 때는 split을 사용했는데 +를 넣을 땐 이스케이프 \\를 앞에 적어주어야 한다. +가 정규식에 해당되어 제대로 나눠지지 않기 때문이다. 참고

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 1541번 잃어버린 괄호
 * - 덧셈 부분을 먼저 계산하기
 */
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str[] = br.readLine().split("-");
		int sum = Integer.MAX_VALUE;
		
		for (int i = 0; i < str.length; i++) {
			String addition[] = str[i].split("\\+");
			int num = 0;
			
			for (int j = 0; j < addition.length; j++) {
				num += Integer.parseInt(addition[j]);
			}
			
			if (sum == Integer.MAX_VALUE) sum = num;
			else sum -= num;
		}
		
		System.out.println(sum);
	}
}