[백준 2024/01/21] 1541번 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

1. 접근 방법

식의 값이 최소가 되기 위해서는, +를 먼저 계산하고

-를 마지막에 계산하게 된다면, -가 가장 커진 상태에서 -를 할 수 있다고 생각하였다.

 

이 문제를 보며, 우선 +와 -를 분리해내야겠다고 생각하였다.

 

만약 분리해낸다면, 50-40+30의 경우 다음과 같은 리스트를 가지게 될 것이다.

[50, 40, 30]

[-,+]

이제 +를 먼저 계산해야하므로, 

+가 operator list에 존재하고 있다면, +의 indexOf를 통해여 index, i를 구하여 주고,

number operator에서 i와 i+1끼리 더해서, 리스트에 넣어주고, 

이전 값들은 지워주었다. 그렇게 된다면 리스트는 다음과 같이 바뀌어 있을 것이다.

 

[50, 70]

[-]

이제는 + 가 operator list에 없으므로, 다음 단계로 넘어가 뺄셈을 해주었다.

이젠 +인지 -인지 구분할 필요 없이 마음 편히 -만 해주면 된다.

 

 expression.split("\\d+");

여기서 \d 는 숫자 한개를 의미하고, +는 하나 이상의 연속된 숫자(문자)를 의미한다.

i like potato scattering smile에서 공백 기준으로 분리하고 싶다면, \\s+ 를 통해서 분리해내는 것과 비슷하다.

\s 는 문자, + 는 문자열을 의미할 것이다.

2. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;


public class b1541 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String expression = reader.readLine();

        List<Integer> list = new ArrayList<>();
        List<String> list_op = new ArrayList<>();

        String[] numbers = expression.split("[+-]");
        String[] operators = expression.split("\\d+");

        for(int i =0; i<numbers.length; i++){
            list.add(Integer.parseInt(numbers[i]));
        }
        list_op.addAll(Arrays.asList(operators));

        if(list_op.size()!=0) {
            list_op.remove(0);
        }

        int sum = 0;
        while(list_op.contains("+")){
            int i = list_op.indexOf("+");
            sum = list.get(i) + list.get(i + 1);
            list.set(i, sum);
            list.remove(i + 1);
            list_op.remove(i);
        }

        int total = list.get(0);

        for(int i =0; i<list_op.size();i++){
            total -= list.get(i+1);
        }

        System.out.println(total);

    }

}