[백준] 14888번(Java)

📖 연산자 끼워넣기

[ 문제 ]

• N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
• 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
• 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
  
  1+2+3-4×5÷6
  1÷2+3+4-5×6
  1+2÷3×4-5+6
  1÷2×3-4+5+6.
  
  
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다..
  
  1+2+3-4×5÷6 = 1
  1÷2+3+4-5×6 = 12
  1+2÷3×4-5+6 = 5
  1÷2×3-4+5+6 = 7.
  
  
• N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

💡풀이

• 백트래킹으로 연산자를 큐에다 하나씩 넣어주고 연산자 방문 표시를 해준다. 이후 큐에 N-1개만큼 연산자가 쌓이면 이대로 연산해주는 opResult 메서드를 실행해서 결과를 반환받고, 이 값이 Max보다 큰지, Min보다 작은지를 검사해 최댓값과 최솟값을 구한다.

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static Deque<String> tmp;
    static int[] num;
    static String[] op;  // 연산자 담는 배열
    static boolean[] visited;
    static int N;
    static int MIN = 1000000000;
    static int MAX = -1000000000;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        num = new int[N]; // 총 N 개의 숫자
        StringTokenizer st = new StringTokenizer(br.readLine());
        visited = new boolean[N-1]; //연산자 방문 여부
        tmp = new ArrayDeque<>();

        for(int i = 0 ; i < N ; i ++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        StringTokenizer st1 = new StringTokenizer(br.readLine());

        sb.append("+".repeat(Integer.parseInt(st1.nextToken())));
        sb.append("-".repeat(Integer.parseInt(st1.nextToken())));
        sb.append("*".repeat(Integer.parseInt(st1.nextToken())));
        sb.append("/".repeat(Integer.parseInt(st1.nextToken())));
        op = sb.toString().split(""); // 무조건 N-1개 size

        btc(0);
        System.out.println(MAX);
        System.out.println(MIN);
    }
    public static void btc(int cnt){
        if(cnt == N - 1){
            MIN = Math.min(MIN, opResult(tmp));
            MAX = Math.max(MAX, opResult(tmp));
            return;
        }
        for(int i = 0 ; i < N - 1 ; i ++){
            if(!visited[i]){
                visited[i] = true;
                tmp.push(op[i]);
                btc(cnt + 1);
                visited[i] = false;
                tmp.pop();
            }
        }
    }
    public static int opResult(Queue<String> op){
        String[] oper = op.toArray(new String[N-1]);
        int res = num[0];

        for(int i = 0 ; i < N -1 ; i ++){
            switch (oper[i]) {
                case "+" :
                    res += num[i + 1];
                    break;
                case "-" :
                    res -= num[i + 1];
                    break;
                case "*" :
                    res *= num[i + 1];
                    break;
                case "/" :
                    res /= num[i + 1];
                    break;
            }
        }
        return res;
    }
}

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