백준 1541 - 잃어버린 괄호 (Java)

 

문제 개요

 

문제 개요

 

---

 

풀이

 

이번 문제의 핵심은 덧셈과 뺄셈만 존재하는 정상적인 수식이 존재할 때, 괄호를 넣는 위치에 따라 결과 값이 달라진다는 것이다. 

 

가령 아래의 두 예시를 보자.

 

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

 

두 예시의 결과 값이 다른 이유는 수식을 계산하는 순서에서 괄호 안의 수식을 우선으로 계산해야 하기 때문이다.

 

이 문제는 백준 알고리즘에서 그리디 알고리즘으로 분류되어 있다.

즉, 최적의 가설을 세우고 이를 코드로 작성해야 한다는 것이다.

 

때문에 나는 최소의 결과 값을 얻기 위해 이런 가설을 세웠다.

 

 

문자열을 검사하면서 '+' 기호가 나오면 이전 수와 다음 수를 누적해서 더해주고,
'-' 기호가 나오면 지금까지 누적되었던 수를 빼도록 괄호를 만들면 최소 값이다.

 

가령 55 - 50 + 45 + 30 - 5 + 60 + 15 라는 수식이 존재할 경우 55 - (50 + 45 + 30) - (5 + 60 + 15) = -150 와 같이 마이너스(-) 기호를 기준으로 수식을 쪼개서 첫 수에서 나눠진 덩어리들의 결과 값을 빼주면 된다.

 

이를 아래와 같은 과정의 코드로 나타낼 것이다.

 

1. 입력은 한 줄이므로 한 줄의 식을 입력받아 String.split('-') 를 통해 식을 쪼개어 배열로 저장한다.
2. 배열의 0번째 인덱스, 즉 첫 덩어리(전체 식에서 '-' 를 기준으로 쪼갠 식들의 첫 번째)를 하나의 변수에 저장한다.
3. 이 후의 덩어리들은 반복문을 통해 각각의 합들을 구한다.
   • 이 때도 String.split() 메서드를 사용한다.
   • String.split() 메서드의 매개변수로 '+'가 아닌 '//+'를 사용할 것이다.
   • '+' 기호는 정규표현식에서 이미 예약어로 사용 중인 기호이기 때문이다.
4. 반복문의 각 루프에서 구해진 수들을 처음에 구했던 첫 덩어리에서 뺀다.
5. 최종적으로 반복문이 종료되면 구한 결과 값을 출력한다.

 

---

 

코드

 

import java.io.*;

public class Main {
    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] items = br.readLine().split("-");
        int answer = 0;

        for (String n : items[0].split("\\+"))
            answer += Integer.parseInt(n);

        for (int i=1 ; i< items.length ; i++) {
            int mid = 0;
            for (String n : items[i].split("\\+"))
                mid += Integer.parseInt(n);

            answer -= mid;
        }
        System.out.println(answer);
        
        return;
    }
}

 

코드 리뷰를 하자면,

 

1. String[] 타입의 변수인 items에 '-'을 기준으로 나눈 식들의 덩어리를 저장한다.
2. 첫 번째 for문에서 items[0] 즉, 첫 덩어리의 수를 구하여 answer변수에 저장한다.
   • 최종적으로는 int형 변수인 answer를 출력할 것이다.
3. 두 번째 fo문에서 이 후의 나눠진 식들의 결과 값을 구한다.
   • 중간 결과로도 볼 수 있다.
   • 이 값은 최소의 결과를 발생시키도록 괄호를 배치했을 때, 각 괄호안의 결과 값이다.
4. answer에 (answer - 각 루프의 중간 결과)를 저장한다.
5. 반복문이 종료되었을 때 answer 값이 문제에서 원하는 식의 최소 값이 되고, 이를 출력해준다.

 

---

 

제출 결과

 

제출 결과

 

이전에 제출했을 대와 비교했을 때 상대적으로 더 적은 코드를 작성했고 더 효율적으로 동작하게 되었다!!