[백준알고리즘] 문자열/그리디 - 1541번 잃어버린 괄호 문제

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

요새 문자열 문제를 안풀어본것 같아서 함 풀어봤다.

-연산자가 나온다면 앞에 있는수는 작게, 뒤에 오는수는 크게 만들어서 풀면 되겠다고 생각했으나

문자열을 어떻게 처리해서 연산시켜야 할지 막막했다..

 

해결방법

관건은 -연산이다. + 연산자들을 묶어서 먼저 합쳐준 뒤 마지막에 그것들을 갖고 -연산을 하면 된다

문자열을 먼저 - 을 구분자로 split함수를 통해 나눠서 배열에 저장하고 (그러면 "1+2", "3", "3+1+5"이런식으로 나눠질것이다)

그렇게 나눠진 것들을 +구분자로 다시 split으로 쪼개어 피연산자들만 배열에 넣어준뒤 합쳐준다

(이때 구분자를 "+"로 하면 원하는대로 인식을 못한다..이스케이프 문자를 써서 "\\+"로 표현해줘야한다..불편하다..)

그렇게 +연산을 해서 하나로 나온 sum값을 순서대로 빼주면 된다

이때 제일 먼저 들어오는 값은 맨 앞에있는 값이라 -연산할게 없으므로 그냥 result에 넣어주면 된다

 

막상 코드는 간단한데 풀이과정이 나에겐 쉽지 않았던 문제이다..

그리디 알고리즘으로 분류되어 있던데 이게 왜 그리디한건지 사실 잘 와닿진 않았다

package baekjoonWeek6;

import java.io.*;

public class BJ_1541 {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] splitByMinus = str.split("-");
        int result = Integer.MAX_VALUE; //첨엔 -1이라고 해놨었다가 틀렸었
        for (int i = 0; i < splitByMinus.length; i++) {
            String[] splitByPlus = splitByMinus[i].split("\\+");
            int sum = 0;
            for (int j = 0; j < splitByPlus.length; j++) {
                sum += Integer.parseInt(splitByPlus[j]);
            }
            if (result == Integer.MAX_VALUE) { //맨 첫번째 값이면 빼지말고 그냥 넣어준다
                result = sum;
            } else {
                result -= sum;
            }
        }
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
    }
}