[JAVA][Baekjoon] 1541번 잃어버린 괄호 🌟🌟🌟

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

📌 접근 방식

🔎 문제 요약 : 수식에 괄호를 적절히 추가해 식의 값을 최소로 만드는 방법을 찾는 문제! 😊

 

1️⃣ '-' 기준으로 나누기

• "-"를 기준으로 수식을 분리
  이때, "-" 이전의 부분은 더해지고, 이후의 부분들은 큰 덩어리로 묶여 모두 빼야 함

2️⃣ '+'로 묶인 숫자들의 합을 구하기

• 덩어리를 '+'로 나누어 각 부분의 합을 계산

3️⃣ 첫 번째 덩어리는 그대로 더하고, 나머지는 모두 빼줍니다.

 

✅ PASS CODE

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

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        // 입력된 수식을 읽어옴
        String example = scanner.nextLine();

        // '-'를 기준으로 수식을 분리
        String[] str = example.split("-");

        // 결과를 저장할 변수
        int sum = 0;

        // '-'로 나눈 각 부분을 처리
        for (int i = 0; i < str.length; i++) {
            if (i == 0) {
                // 첫 번째 덩어리는 무조건 더해줌
                sum += mySum(str[i]);
            } else {
                // 이후 덩어리는 모두 빼줌
                sum -= mySum(str[i]);
            }
        }

        // 최종 결과 출력
        System.out.println(sum);
    }

    // 문자열 덩어리에서 '+'로 나누어 합을 계산하는 함수
    public static int mySum(String a) {
        int sum = 0;

        // '+'를 기준으로 숫자를 분리
        String[] tmp = a.split("[+]");

        // 각 숫자를 더해줌
        for (int i = 0; i < tmp.length; i++) {
            sum += Integer.parseInt(tmp[i]);
        }

        return sum; // 계산된 합 반환
    }
}

✅ String[] tmp = a.split("[+]"); 에서 [+]를 사용하는 이유

1️⃣ +의 역할

• 정규 표현식에서 +는 앞의 패턴이 하나 이상 반복된다는 의미로 사용됨
• 예를 들어, "a+"는 "a", "aa", "aaa"와 같은 문자열에 매치됨

2️⃣ 일반 문자로 인식시키기

• 우리가 원하는 건 수식의 '+' 기호를 기준으로 문자열을 나누는 것이지, 정규 표현식에서의 + 역할이 아님
• 따라서 '+'를 일반 문자로 인식시키기 위해서는 문자 클래스인 [+]를 사용해야 함
  ➡️ [+]는 +라는 문자 자체를 의미

3️⃣ 대안: Escape 처리

• 정규 표현식에서 메타문자를 일반 문자로 사용하려면 백슬래시(\)를 사용해 Escape 처리할 수도 있음
  String[] tmp = a.split("\\+");
  
  

😊 느낀 점

처음에는 괄호를 어디에 넣을지 직접 고민하고 덧셈, 뺄셈에선 괄호가 계산 순서에 영향이 없지 않은가? 생각했다. 문제를 분석해보니 빼기 이후 숫자들을 모두 더해 한 번에 빼는 것이 최적의 해라는 사실을 알게 되었다! 👍

그리디 알고리즘처럼 현재의 최적 선택이 전체에서도 최적임을 증명할 수 있는 문제였다