[Java] 백준 1541 : 잃어버린 괄호

문제 링크

1.

문제를 보고 답을 내는 메커니즘 자체는 쉽게 생각해냈다.

다만, 입력받은 문자열을 어떻게 쉽고 효율적으로 가공할지 몰라서 풀이를 참고하였다.

 

 

2.

그리디 알고리즘을 적용하면, 괄호를 넣어 식의 값을 최소로 만들려면 최대한 많은 수를 음수로 만들어야 한다.

 

즉, $-$가 나오고 다음 $-$가 나오기 전까지 괄호로 묶으면 되는데, 이 말은 곧 $-$와 $-$사이의 $+$를 $-$로 바꾸면 된다.

 

예를 들어보면,

$1+2+3-4+5+6-7+8$ 이라면

$1+2+3-(4+5+6)-(7+8)$ 으로 괄호를 치는 것이 최소가 된다.

이는 곧 $1+2+3-4-5-6-7-8$과 같다.

 

 

이를 메커니즘으로 나타내면 다음과 같다.

1. 입력받은 문자열을 $-$를 기준으로 분리

2. 분리한 문자열을 차례대로 순회하며

   2.1 $+$를 기준으로 분리

   2.2 분리한 문자열을 덧셈 계산을 한 후

   2.3 정답에서 빼주기 (단, 양수가 제일 먼저 오므로 첫 번째에는 더해주기)

 

 

3.

import java.util.Scanner;

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

        String temp = sc.nextLine();
        String[] str = temp.split("\\-");

        int answer = 0;
        for (int i = 0; i < str.length; i++) {
            String[] subStr = str[i].split("\\+");

            int calc = 0;
            for (String item : subStr) {
                calc += Integer.parseInt(item);
            }

            if (i == 0) {
                answer += calc;
            } else {
                answer -= calc;
            }
        }

        System.out.println(answer);
        sc.close();
    }
}

 

 

4.

문자열을 분리할 때 substring 메소드보다는 split 메소드를 주로 활용한다.

split 메소드에서 특수문자를 기준으로 분리할 때 \\를 붙여 주어야 한다.

 

[참고] https://plplim.tistory.com/30

[참고] https://soulduse.tistory.com/36