백분 알고리즘 - 연산자 끼워넣기
다행히도 연산할 때 우선순위가 없다.
무조건 앞쪽부터 차례대로 연산해서 고려 할게 줄었다.
+-*/ 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;
}
}
}
}
무조건 앞쪽부터 차례대로 연산해서 고려 할게 줄었다.
+-*/ 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;
}
}
}
}
댓글
댓글 쓰기