알고리즘/카카오
2020 카카오 인턴십수식 - 최대화
BSHwan
2020. 9. 15. 11:25
반응형
import java.util.ArrayList;
public class Solution {
static char[] arr = { '*', '+', '-' };
static int N = 3;
static ArrayList<Long> exp = new ArrayList();
static ArrayList<Character> operations = new ArrayList();
static long answer = Long.MIN_VALUE;
public static long solution(String expression) {
String n = "";
for(int i=0; i<expression.length(); i++) {
if(expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {
n += expression.charAt(i);
} else {
exp.add(Long.parseLong(n));
n = "";
operations.add(expression.charAt(i));
}
if(i == expression.length()-1) exp.add(Long.parseLong(n));
}
perm(0);
return answer;
}
public static void perm(int depth) {
if (depth == N) {
answer = Math.max(Math.abs(calc(arr)), answer);
return;
}
for (int i = depth; i < N; i++) {
rightRotate(depth, i);
perm(depth + 1);
leftRotate(depth, i);
}
}
public static Long calc(char[] priority) {
ArrayList<Long> num = new ArrayList(exp);
ArrayList<Character> ops = new ArrayList(operations);
for(int i=0; i<priority.length; i++) {
for(int j=0; j<ops.size(); j++) {
if(priority[i] == ops.get(j)) {
long result = 0;
if(ops.get(j) == '*') {
result = num.get(j) * num.get(j+1);
} else if(ops.get(j) == '+') {
result = num.get(j) + num.get(j+1);
} else if(ops.get(j) == '-') {
result = num.get(j) - num.get(j+1);
}
num.set(j, result);
num.remove(j+1);
ops.remove(j);
j--;
}
}
}
return num.get(0);
}
public static void leftRotate(int s, int e) {
char temp = arr[s];
for (int i = s; i < e; i++) {
arr[i] = arr[i + 1];
}
arr[e] = temp;
}
public static void rightRotate(int s, int e) {
char temp = arr[e];
for (int i = e; i > s; i--) {
arr[i] = arr[i - 1];
}
arr[s] = temp;
}
}
반응형