[백준 1541] 잃어버린 괄호 (JAVA)

백준 1541번 문제  - 잃어버린 괄호

1541번: 잃어버린 괄호

---

문제 분석

 

• 문자열이 주어지면 해당 문자열이 실제로 계산될 때 괄호를 사용해 최솟값을 만들어 출력해라 

---

 

해결 키 포인트

 

• 그리디 알고리즘
• 최솟값을 만들기 위해서는 최대로 많은 수가 - 되야 한다.
  • 즉, 괄호를 - 앞 뒤에 두어야 함
• - 앞 뒤 문자열, + 앞 뒤 문자열을 나누기 위해 split 를 사용
  • s.split("-")
  • s.split("\\+")

s.split("+")로 하면,
java.util.regex.PatternSyntaxException: Dangling meta character ‘+’ near index 0 에러 발생

Why?  + 가 특별한 의미로 쓰이기 때문이다. 그러므로 이를 사용하고 싶을 때는 "\\+" 로 해줘야 한다.

+ 기호 말고도 * 과 ^ 으로 나눌 때도 마찬가지이다.

 

---

그리디 알고리즘 (탐욕 알고리즘)

 

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

쉽게 말해, 지금의 최선 = 전체의 최선

 

뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 
서울에서 대구의 최솟 값을 선택하고, 대구에서 부산까지의 최솟값을 선택하는 알고리즘

파이썬 알고리즘 인터뷰 (나무위키)

 

---

코드

import java.io.*;

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

        // 수 입력
        String s = br.readLine();

        int result = 0;

        // - 로 문자를 분리
        String [] minusNum = s.split("-");

        // 해당 문자열 수만큼 반복
        for(int i=0;i<minusNum.length;i++) {
            // + 로 문자를 분리
            String [] plusNum = minusNum[i].split("\\+");

            int sum = 0;
            // 해당 문자열 수만큼 반복
            for(int j=0;j<plusNum.length;j++) {
                // 모두 더한다
                sum += Integer.parseInt(plusNum[j]);
            }
            // index가 0일 경우에는 result가 더한 값
            if(i == 0)
                result = sum;
            // index가 0 이상일 경우에는 result에서 sum값을 뺀다.
            else
                result -= sum;
        }

        System.out.println(result);

    }
}