[Java] 백준(실버-2) 1541번 - 잃어버린 괄호

문제 풀이

---

이 문제는 그리디 알고리즘 유형의 문제 중 하나이다.

아이디어 도출

주어진 문자열 식을 보고 괄호를 쳐서 식의 결과를 가장 최솟값으로 나오도록 해야한다. 어떻게 괄호를 쳐 식의 결과를 최소로 만들 수 있을까?

하나의 예시를 보자.

input = 30-70-20+40-10+100+30-35
30 - 70 - (20+40) - (10+100+30) - 35 = -275

위 예시를 보면 알겠지만 핵심 포인트는 바로 덧셈 부분을 먼저 계산 하는 것이다. 이를 통해 문제 해결을 위한 아이디어는 다음과 같다.

1. 뺄셈(-)을 기준으로 주어진 문자열 식을 분할한다.
2. 분할된 문자열 각각을 하나의 원소로 모두 더해준다.
3. 뺄셈으로 분할된 원소들을 뺄셈해준다.

추가적으로 문제 풀이시 유의해야 할 것은 다음과 같다.

• 식의 첫번째 수는 양수인 점을 유의해야 하기 때문에, 첫번째 수를 초기값으로 설정하도록 해야 한다.
• split() 메서드 사용시 PatternSyntaxException 예외 방지를 위해 ”\+” 로 escape 처리 해야한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String input = br.readLine();
        String[] split_minus = input.split("-");
        int min = 0;

        for(int i=0; i<split_minus.length; i++) {
            
            // 뺄셈으로 나뉜 수들을 더할 num 변수 선언 및 초기화
            int num = 0;
            
            // 그냥 "+"으로 split 메서드를 사용하면 + 문자는 메타문자라서 PatternSyntaxException 에러가 발생한다.
            // 그래서 + 문자를 이용하기 위해 "\\+"로 escape 처리를 한다.
            // 이후, +로 분할된 원소를 모두 num에 더해준다.
            String[] split_plus = split_minus[i].split("\\+");
            for(String num_plus : split_plus) {
                num += Integer.parseInt(num_plus);
            }
            
            // 첫번째 수는 양수이기에 초기값으로 설정한다.
            // 첫번째 수가 아니라면 모두 뺄셈해준다.
            if(i==0) {
                min = num;
            } else {
                min -= num;
            }

        }
        
        bw.write(min+"\n");

        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.