백준 Q14888 연산자 끼워넣기

---

로직 설계

1. 숫자 배열과 연산자 배열을 만들어서 배열의 조합을 백트래킹하여 연산

실패 과정...

st = new StringTokenizer(br.readLine());
for(int i=0; i<4; i++){
    // 0 : 덧셈, 1 : 뺄셈, 2: 곱셈, 3: 나눗셈
    operators[i] = Integer.parseInt(st.nextToken());
}

다음과 같이 입력 받는 값을 그대로 사이즈가 4인 연산자 배열에 넣어두고 Map에서와 같이 카운트를 빼주는 식으로 백트래킹을 하려고 했으나 과부하가 걸렸다,,

private static void dfs(int current, int value){
    if(checkOperators()) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        return;
    }
    int bfValue = value;
    for(int i=current+1; i<list.size(); i++){
        int operator = selectOperator(i);
        if(operator == 0 && !visited[i][0]){
            visited[i][0] = true;
            value += list.get(i);
        } else if(operator == 1 && !visited[i][1]){
            visited[i][1] = true;
            value -= list.get(i);
          } else if(operator == 2 && !visited[i][2]){
            visited[i][2] = true;
            value *= list.get(i);
        } else if(operator == 3 && !visited[i][3]){
            visited[i][3] = true;
            if(value < 0) {
                value = (Math.abs(value) % list.get(i)) * -1;
            } else {
                value = value % list.get(i);
            }
        } else if(operator == 4){
            dfs(i--, value);
        }
        dfs(i, value);
        operators[operator]++;
        value = bfValue;
    }
}

처음엔 위와같이 설계했으나 원하는 연산자가 백트래킹이 되는 것이 아닌 숫자가 백트래킹되는 현상을 겪어서 조금만 단순하게 생각하기로 했다.

정답 코드

---

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

public class Q14888_연산자_끼워넣기 {
    static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static List<Integer> numbers = new ArrayList<>();
    static List<Integer> operators = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers.add(Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            // 0 : 덧셈, 1 : 뺄셈, 2: 곱셈, 3: 나눗셈
            int operator = Integer.parseInt(st.nextToken());
            for (int j = 0; j < operator; j++) {
                operators.add(i);
            }
        }
        visited = new boolean[N - 1];
        List<Integer> temp = new ArrayList<>();
        dfs(0, temp);
        System.out.println(max + "\n" + min);
    }

    private static void dfs(int current, List<Integer> temp) {
        if (temp.size() == operators.size()) {
            solution(temp);
            return;
        }
        for (int i = 0; i < operators.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                temp.add(operators.get(i));
                dfs(i, temp);
                visited[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }

    private static void solution(List<Integer> temp) {
        int value = numbers.get(0);
        for (int i = 0; i < temp.size(); i++) {
            int operator = temp.get(i);
            if (operator == 0) {
                value += numbers.get(i + 1);
            } else if (operator == 1) {
                value -= numbers.get(i + 1);
            } else if (operator == 2) {
                value *= numbers.get(i + 1);
            } else if (operator == 3) {
                if (value < 0) {
                    value = (Math.abs(value) / numbers.get(i + 1)) * -1;
                } else {
                    value = value / numbers.get(i + 1);
                }
            }
        }
        max = Math.max(max, value);
        min = Math.min(min, value);
    }
}

달라진 점은 기존의 Map형식처럼 연산자 배열을 만드는 것이 아닌
0: 덧셈 1: 뺄셈 2: 곱셈 3: 나눗셈 으로 연산자에 번호를 지명해두고 리스트에 담은 뒤 나오는 조합마다 연산자의 index와 연산할 숫자의 index를 매칭시켜 계산해나가는 방식으로 풀었다.
그림으로 조금 더 알기 쉽게 그려보겠다.
ex)