백준 1541 잃어버린 괄호 Java: 첫 번째 마이너스 뒤를 모두 빼는 이유

백준 1541번 ‘잃어버린 괄호’는 식에서 첫 번째 -가 나온 뒤의 수를 모두 빼면 최솟값을 만들 수 있다. - 뒤에서 다음 - 전까지의 덧셈을 괄호로 묶으면 그 구간 전체에 음수 부호를 적용할 수 있기 때문이다.

• 백준 1541번 잃어버린 괄호

왜 첫 번째 마이너스가 기준인가

다음 식을 보자.

A - B + C + D - E + F

뺄셈 뒤의 덧셈을 괄호 안으로 넣으면 다음처럼 만들 수 있다.

A - (B + C + D) - (E + F)

B, C, D, E, F가 모두 빠지므로 원래 식보다 작거나 같다. 입력의 수는 음수가 아니기 때문에 첫 번째 - 이후에 다시 더해야 이득인 항은 없다.

따라서 식을 -로 먼저 나누고, 첫 구간의 합에서는 나머지 구간의 합을 모두 뺀다.

55-50+40
= 55-(50+40)
= -35

Java 코드

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

public class Main {
    private static int sumGroup(String group) {
        String[] numbers = group.split("\\+");
        int sum = 0;

        for (String number : numbers) {
            sum += Integer.parseInt(number);
        }

        return sum;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );

        String expression = reader.readLine();
        String[] groups = expression.split("-");

        int answer = sumGroup(groups[0]);

        for (int i = 1; i < groups.length; i++) {
            answer -= sumGroup(groups[i]);
        }

        System.out.println(answer);
    }
}

+는 정규 표현식에서 특별한 의미가 있으므로 split("\\+")처럼 escape한다. Integer.parseInt("00009")는 9를 반환하므로 앞에 붙은 0을 따로 제거할 필요는 없다.

처음 헷갈렸던 지점

원문 기록에는 첫 번째 예제 55-50+40의 답이 왜 -35인지 약 5분 동안 이해하지 못했다고 적혀 있었다. 55-50+40을 왼쪽부터 계산하는 데 머물렀다가 55-(50+40)처럼 괄호를 새로 칠 수 있다는 점이 단서가 됐다.

그 뒤에는 “첫 번째 마이너스를 만난 뒤부터는 전부 뺀다”는 규칙을 잡았다. 당시에는 연산자와 숫자를 substring()으로 하나씩 잘랐지만, - 구간과 + 항을 차례로 나누면 같은 생각을 더 짧게 표현할 수 있다.

복잡도와 경계 확인

식의 길이를 L이라고 하면 문자열을 한 번씩 나누고 모든 숫자를 한 번 더하므로 시간 복잡도는 O(L), 분리한 문자열을 저장하는 공간은 O(L)이다.

• 마이너스가 없으면 첫 구간의 덧셈 결과가 그대로 답이다.
• 00009-00009처럼 선행 0이 있어도 정수 변환 결과는 0이다.
• 첫 번째 수까지 빼면 안 된다. 첫 - 앞의 구간은 모두 더한다.

같은 그리디 분류라도 선택 근거가 다른 예시는 백준 13305 주유소에서 비교할 수 있다.

검증 범위

Java source를 수동 검토하고 보존된 세 예제와 작은 식의 가능한 괄호 결과를 독립 oracle로 대조했다. 2026년 8월 2일 현재 BOJ 문제 URL은 채점 서비스 준비 화면을 표시해 현행 judge 재제출은 확인하지 못했다.