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

guswls·2024년 5월 5일

알고리즘

목록 보기

18/39

문제

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

코드

import java.util.*;
import java.io.*;

//55-50+40
//55-(50+40) -> -35가 답
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		String[] nums = input.split("[+,-]");
		String[] opers = input.replaceAll("[0-9]", "").split("");

		String prev = opers[0];
		for (int i = 1; i < opers.length; i++) {
			if (prev.equals("-")) {
				opers[i] = "-";
			}
			prev = opers[i];
		}

		int ret = Integer.parseInt(nums[0]);
		for (int i = 1; i < nums.length; i++) {
			String op = opers[i - 1];

			if (op.equals("-")) {
				ret -= Integer.parseInt(nums[i]);
			} else {
				ret += Integer.parseInt(nums[i]);
			}

		}
		
		System.out.println(ret);
	}
}

문제 이해

+, -로 이루어진 수식에서 괄호를 적당히 쳐서 연산결과가 최소값이 되도록 하는 문제이다.
이때 주목할 것은 연산자가 +, -밖에 없다는 것이다.
괄호를 친다면 +는 -, -는 +가 된다.
이를 이용하면 원하는 결과에 도출할 수 있다. 즉, 괄호를 쳐서 -뒤에 있는 값을 최대한 크게, +를 -로 변경하면 된다.
이것을 그대로 풀이로 옮기면 된다.

풀이 방법

우선 수식에서 숫자만 파싱한 nums, 기호만 파싱한 opers를 준비한다.
opers에서 -이후의 +문자를 모두 -로 변경한다. 이때 prev가 +가 되면 아무것도 하지 않고 건너뛴다.
위 동작이 곧 괄호를 쳐서 수식의 결과를 최소로 만드는 중요한 과정이다.
그 뒤로는 nums와 opers를 순회하며 +면 더하고, -면 빼는 과정을 수행하면 된다.
이를 통해 수식의 결과를 최소로 만들 수 있다.

핵심 포인트

위에서 언급한대로, 괄호를 적당히 쳐서 수식의 결과를 최소가 되는 방법을 정확히 파악해야 한다.
-뒤의 +를 -로 변경해준다고 생각하면 이해가 쉽다.
정규식을 활용한 파싱에 유의해야 한다. opers를 구성할 때 .split("[\\d]로 숫자만 빼서 파싱하려 했는데 공백이 계속 추가됐다.
이 부분을 해결하지 못해서 .replaceAll("[0-9]", "")로 변경하는 방법을 구글링으로 찾아냈다.