[백준 알고리즘 / JAVA] 1541번 잃어버린 괄호

---

문제 정보

• 문제 링크: https://www.acmicpc.net/problem/1541
• 문제 번호: 1541번
• 문제 이름: 잃어버린 괄호
• 문제 난이도: 실버2
• 반복 학습 날짜
  • 2024.01.25 완료

1541번: 잃어버린 괄호

---

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 입력을 받기 위해 BufferedReader를 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 수식을 '-'를 기준으로 나누어 배열에 저장
        String[] mathExpression = br.readLine().split("-");
        
        // 최소 합을 저장할 변수 초기화
        int minSum = Integer.MAX_VALUE;
        
        // '-'로 나눈 각 부분 수식에 대해 계산 수행
        for(int i = 0; i < mathExpression.length; i++) {
            int summary = 0;
            
            // '+'를 기준으로 나눈 각 항을 더하여 summary에 저장
            String[] mathExpression2 = mathExpression[i].split("\\+");
            for(int j = 0; j < mathExpression2.length; j++) {
                summary += Integer.parseInt(mathExpression2[j]);
            }
            
            // 최소 합 갱신
            if(minSum == Integer.MAX_VALUE) {
                minSum = summary;
            } else {
                minSum -= summary;
            }
        }
        
        // 결과 출력
        System.out.println(minSum);
    }
}

---

풀이

Step1: 수식 처리를 통한 최소 합 구하기

// 수식을 '-'를 기준으로 나누어 배열에 저장
String[] mathExpression = br.readLine().split("-");

// 최소 합을 저장할 변수 초기화
int minSum = Integer.MAX_VALUE;

// '-'로 나눈 각 부분 수식에 대해 계산 수행
for(int i = 0; i < mathExpression.length; i++) {
    int summary = 0;

    // '+'를 기준으로 나눈 각 항을 더하여 summary에 저장
    String[] mathExpression2 = mathExpression[i].split("\\+");
    for(int j = 0; j < mathExpression2.length; j++) {
        summary += Integer.parseInt(mathExpression2[j]);
    }

    // 최소 합 갱신
    if(minSum == Integer.MAX_VALUE) {
        minSum = summary;
    } else {
        minSum -= summary;
    }
}

문제에서 주어진 예제는 55-50+40입니다. 여기서 나올 수 있는 값은 다음과 같습니다.

1. (55-50)+40 = 45

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

 

두 가지의 경우의 수가 발생하는데, 위의 예시에서 보면 다음과 같이 순서를 지정할 수 있습니다.

1. 수식에서 덧셈 부분을 먼저 더한다.

2. 뺄 샘을 수행한다.

 

두 가지의 공식을 코드에 적용해 보았을 때, 가장 먼저 "-"를 기준으로 식을 나누고 난 후 그 값들은 "+"기준으로 나눈 후 더합니다. 그 이후 차례대로 뺄셈을 수행하며 최솟값을 갱신합니다.