백분 알고리즘 - 연산자 끼워넣기

다행히도 연산할 때 우선순위가 없다.
무조건 앞쪽부터 차례대로 연산해서 고려 할게 줄었다.

+-*/ 4가지의 개수를 String 배열에 담았다.
인풋이 2 1 2 1 이면 "+", "+", "-", "*", "*", "/"
그 후 DFS로 끝까지 탐색 할 때마다 연산하고 값을 HashSet에 담았다.
그리고 최소값, 최대값을 출력해 주었다.

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

//+ - * /
public class Main {
    private static int max = 0;
    private static int min = 0;
    private static int[] sequence;
    private static String[] operators;
    private static boolean[] isVisit;

    private static String[] resultOp;
    private static HashSet<Integer> resultSet = new HashSet<>();

    private static int[] resultArr = new int[2];

    private static int oIdx = 0;

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int numCnt = Integer.parseInt(scn.nextLine());
        String sequenceStr = scn.nextLine();
        String[] sequencesString = sequenceStr.split(" ");
        sequence = new int[sequencesString.length];
        for (int i = 0; i < numCnt; i++) {
            sequence[i] = Integer.parseInt(sequencesString[i]);
        }

        operators = new String[sequence.length - 1];
        isVisit = new boolean[sequence.length - 1];
        resultOp = new String[sequence.length - 1];

        String operatorStr = scn.nextLine();
        String[] operatorsString = operatorStr.split(" ");

        insertOp("+", operators, Integer.parseInt(operatorsString[0]));
        insertOp("-", operators, Integer.parseInt(operatorsString[1]));
        insertOp("*", operators, Integer.parseInt(operatorsString[2]));
        insertOp("/", operators, Integer.parseInt(operatorsString[3]));

        for (int i = 0; i < operators.length; i++) {
            isVisit[i] = true;
            DFS(operators, isVisit, operators[i], operators.length, 0);
            isVisit[i] = false;
        }
        if (operators.length > 1) {
            Iterator iterator = resultSet.iterator();
            int firstVal = (Integer) iterator.next();
            max = firstVal;
            min = firstVal;
            while (iterator.hasNext()) {
                int thisVal = (Integer) iterator.next();
                if (min > thisVal) {
                    min = thisVal;
                }
                if (max < thisVal) {
                    max = thisVal;
                }
            }
            System.out.println(max);
            System.out.println(min);
        } else {
            System.out.println(resultArr[0]);
            System.out.println(resultArr[1]);
        }
    }
    private static void insertOp(String type, String[] op, int time) {
        for (int i = 0; i < time; i++) {
            op[oIdx] = type;
            oIdx++;
        }
    }
    private static void DFS(String[] op, boolean[] visit, String start, int last, int depth) {
        resultOp[depth] = start;
        if (depth == last - 1) {
            int calculated = sequence[0];
            for (int i = 0; i < last; i++) {
                if (last == 1) {
                    switch (resultOp[i]) {
                        case "+":
                            calculated += sequence[i + 1];
                            break;
                        case "-":
                            calculated -= sequence[i + 1];
                            break;
                        case "*":
                            calculated *= sequence[i + 1];
                            break;
                        case "/":
                            calculated /= sequence[i + 1];
                            break;
                    }
                    resultArr[0] = calculated;
                    resultArr[1] = calculated;
                } else {
                    switch (resultOp[i]) {
                        case "+":
                            calculated += sequence[i + 1];
                            break;
                        case "-":
                            calculated -= sequence[i + 1];
                            break;
                        case "*":
                            calculated *= sequence[i + 1];
                            break;
                        case "/":
                            calculated /= sequence[i + 1];
                            break;
                    }
                }
            }
            resultSet.add(calculated);
        } else {
            for (int i = 0; i < last; i++) {
                if (visit[i])
                    continue;
                visit[i] = true;
                DFS(op, visit, op[i], last, depth + 1);
                visit[i] = false;
            }
        }
    }

}

댓글

이 블로그의 인기 게시물

About JVM Warm up

About idempotent

About Kafka Basic

About ZGC

sneak peek jitpack

Spring Boot Actuator readiness, liveness probes on k8s

About Websocket minimize data size and data transfer cost on cloud

About G1 GC

대학생 코딩 과제 대행 java, python, oracle 네 번째