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

 

<문제 분석>

1. 첫번째 수는 무조건 양수가 온다고 했으니 그 수에서 뺀값이 가장 작으려면 뒤에 -가 붙는 수가 가장 큰수여야 한다.

2. - 기호가 나오면 그 뒤로 나오는 수들을 모두 더해서 음수로 된 최대값을 만들어야 한다.

3. - 기호가 나오기 전까지의 숫자는 계속 더해주다가 - 기호가 나오면 거기서 괄호를 쳐서 모두 더해서 빼면 된다.

ex)

55-50+40 = 55 - (50 + 40) = 55 - 90 = -35

10+55-50+40 = 10+55 - (50+40) = 65 - 90 = -25

 

<문제 풀이>

1. 3개의 구현이 필요하다.

  1-1. 입력 받은 문자열을 -를 기준으로 잘라서 문자열 배열에 담는 작업

  1-2. 자른 문자열을 +를 기준으로 수를 뽑아내어서 더하는 작업

  1-3. 각 취합된 수를 빼는 작업

2. 첫번째 수에 0이 올수 있기 때문에 sum의 초기값은 0이 아니어야 한다.

 

<코드 구현>

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

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

public class Main {
    static String str;

    void InputData() {
        Scanner in = new Scanner(System.in);
        str = in.next();

    }

    /* 최소값을 구하려면 - 부호가 붙은 수가 커야 한다.
    1. 입력받은 문자열을 빼기(-) 부호를 기준으로 토큰으로 나눈다.
    2. 일차로 분리한 토큰에서 덧셈(+) 부호를 기준으로 분리해서 합산한다.
    3. 첫번째 값에서부터 합산한 값들을 차례대로 빼면 된다.
    4. 첫번째 수에 0이 올수 있기 때문에 sum의 초기값은 0이 아니어야 한다.
    */
    int sum = Integer.MAX_VALUE;
    void Solve() throws Exception {
        String[] sub = str.split("-"); // -로 문자열을 자른다.

        for (int i=0; i<sub.length; i++) {
            int temp = 0;
            String[] add = sub[i].split("\\+"); // 뺄셈으로 나눈 토큰들을 다시 덧셈을 기준으로 분리한다.
            // 덧셈으로 나눈 토큰들을 모두 더한다.
            for (int j=0; j<add.length; j++) {
                temp += Integer.parseInt(add[j]);
            }
            // 첫번째 값에서부터 뺀다.
            // 조건에서 첫번째 수가 0이 올수 있다고 했으니 초기값을 0으로 하면 안된다.
            if (sum == Integer.MAX_VALUE) {
                sum = temp; // sum이 아직 초기값이므로 temp가 첫번재 수이다.
            } else {
                sum -= temp;
            }
        }
        System.out.println(sum);
    }

	public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<후기>

1. 그리디 알고리즘은 어떤 것은 쉽게 풀리고, 어떤 것은 아이디어가 생각이 안나다가 풀이를 보면 아~! 하는 문제가 있다.

2. 나에게는 DFS, BFS 보다 어떨 때는 더 어렵게 느껴지기도 한다.

3. 두번째 풀어보는 문제였는데 풀이방법은 생각이 났는데 문자열을 분리하는 방식이 생각이 나질 않았다.