[알고리즘] 잃어버린 괄호 (백준 1541번)

1541번: 잃어버린 괄호

 +, - 연산자로만 이루어진 수식에서 적절하게 괄호를 쳐서 최소값을 찾아내야하는 문제다.

 

 만약 1+2+3-4+5+6-7 가 있다면 괄호 없이 계산할 시 합은 6이다. 하지만 만약 1+2+3-(4+5+6)-7 로 괄호를 쳐서 계산하게 되면 -16이 답이된다. 즉 -부호가 붙은 뒤의 수들을 괄호로 묶으면 최소값이 된다. (이중괄호는 고려하지 않는다)

 

1. "-" 연산자를 기준으로 String을 split한다.
2. split된 token들을 반복문을 돌려서 token마다 다시 "+"연산자를 기준으로 토크나이즈해서 더한다. (subtract += Integer.parseInt(strtok.nextToken() )
3. 현재 token이 첫 번째 token인 경우엔 result에 더해준다 (result += subtract)
   1. 위의 예시에 따르면 1+2+3의 경우이다.
4. 현재 token이 첫 번째 token이 아니라면 최종결과값 result에서 빼준다. (result -= subtract)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {


    public static void main(String[] args) {

        try
        {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String origin = br.readLine();

            //뺄셈으로 바꿀 단위들로 전환 ex) -40+50+60 => - (40 + 50 + 60)
            ArrayList<String> list = new ArrayList<>(Arrays.asList(origin.split("\\-")));

            int result = 0;

            for(int i = 0;i < list.size();i++)
            {
                StringTokenizer strtok = new StringTokenizer(list.get(i), "\\+");

                int subtract = 0;

                while(strtok.hasMoreTokens())
                    subtract += Integer.parseInt(strtok.nextToken());

                //첫 번째 수는 앞에 -부호가 없으므로 더하기
                if(i == 0)
                    result += subtract;
                else
                    result -= subtract;
            }

            System.out.println(result);
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }

    }

}