[백준] 15659번 : 연산자 끼워넣기(3) java

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

15659번: 연산자 끼워넣기 (3)

 

풀이

풀이 자체는 브루토포스 이지만,  '식의 계산은 연산자 우선 순위를 이용해 계산해야 한다'
라는 문장에서 많이 막혔을 것이다... 나도 풀이가 도저히 떠오르지 않아서 찾아봤다 ...
우선순위 계산할땐 Deque자료구조를 이용하여 풀면된다.
연산자가 +,  -  이면 우선순위가 낮으니 Deque의 마지막에 넣어주고,
연산자가 *, /  이면 우선순위가 높으니 즉시 Deque 마지막 숫자를 꺼내 계산해주는 식으로 풀면된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    private static int N;
    private static int[] arr;
    private static int[] operator = new int[4];
    private static int max = Integer.MIN_VALUE;
    private static int min = Integer.MAX_VALUE;
    private static char[] cal;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        cal = new char[N - 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) operator[i] = Integer.parseInt(st.nextToken());

        dfs(0);

        System.out.println(max);
        System.out.println(min);
    }

    private static void dfs(int depth) {

        if (depth == N - 1) {
            calculateResult();
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (operator[i] == 0) continue;

            cal[depth] = getOperatorBySeq(i);

            operator[i]--;
            dfs(depth + 1);
            operator[i]++;
        }
    }

    private static void calculateResult() {

        Deque<Integer> numStack = new LinkedList<>();
        Deque<Character> operatorStack = new LinkedList<>();
        numStack.add(arr[0]);

        for (int i = 0; i < cal.length; i++) {
            char operator = cal[i];

            switch (operator) {
                case '+': case '-' :
                    operatorStack.addLast(operator);
                    numStack.addLast(arr[i + 1]);
                    break;
                case '*':
                    numStack.addLast(numStack.pollLast() * arr[i + 1]);
                    break;
                case '/':
                    numStack.addLast(numStack.pollLast() / arr[i + 1]);
                    break;
            }
        }

        int result = numStack.poll();

        while (!operatorStack.isEmpty()) {
            Character operator = operatorStack.poll();

            Integer num = numStack.poll();

            if (operator == '+') result += num;
            if (operator == '-') result -= num;
        }


        max = Math.max(result, max);
        min = Math.min(result, min);

    }


    private static char getOperatorBySeq(int i) {

        if (i == 0) return '+';
        if (i == 1) return '-';
        if (i == 2) return '*';
        if (i == 3) return '/';

        throw new RuntimeException("잘못된 요청");
    }
}