백준 1541: 잃어버린 괄호

문제 요약

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

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

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

문제 분류

• 수학
• 그리디 알고리즘
• 문자열
• 파싱

문제 풀이

그리디 방식으로 푸는 문제이다. 가장 작은 수를 만들기 위해서는 뺄셈을 기준으로 왼쪽은 가장 작게, 오른쪽은 가장 크게 만들어야한다. 이렇게 하기 위해서는 덧셈부터 먼저 연산하면 된다. 덧셈을 모두 하고 뺄셈을 할 때는, 빼는 값이 항상 해당 항에서 가장 크기 때문이다.
split("-")을 이용해서 뺄셈을 기준으로 항을 나눠주고, 해당 항을 다시 split("\\+")을 이용해서 덧셈을 기준으로 항을 나누어 모두 더해준다. 뺄셈의 첫 항은 초기화해준 후, 이후의 항들은 모두 뺄셈을 해준다.
+를 기준으로 문자열을 나눌 때는 \\+로 이스케이프 해주어야 한다. 정규표현식과 관련이 있는 듯.

풀이 코드

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split("-");
		String[] p;
		int res = 0, cur;
		for(int i = 0; i < s.length; i++) {
			p = s[i].split("\\+");
			cur = 0;
			for(int j = 0; j < p.length; j++)
				cur += Integer.parseInt(p[j]);
			if(i == 0) res = cur;
			else res -= cur;
		}
		System.out.println(res);
	}
}