programmers.co.kr/learn/courses/30/lessons/67257
코딩테스트 연습 - 수식 최대화
IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과
programmers.co.kr
class Solution {
public long solution(String expression) {
ArrayList<Long> numbers = new ArrayList<Long>();
ArrayList<Character> operator = new ArrayList<Character>();
StringTokenizer st = new StringTokenizer(expression, "+|-|*|/");
while (st.hasMoreTokens()) {
numbers.add(Long.parseLong(st.nextToken()));
}
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) < '0' || expression.charAt(i) > '9') {
operator.add(expression.charAt(i));
}
}
char order[] = new char[4];
boolean check[] = new boolean[4];
max =0;
permu(0, 0, order, numbers, operator, check);
long answer = max;
return answer;
}
// 0=+, 1=-, 2=*, 3=/
static long max;
private void permu(int idx, int cnt, char[] order, ArrayList<Long> numbers, ArrayList<Character> operator,
boolean[] check) {
if (cnt == 4) {
ArrayList<Long> copyNumbers = new ArrayList<Long>();
copyNumbers.addAll(numbers);
ArrayList<Character> copyOperator = new ArrayList<Character>();
copyOperator.addAll(operator);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < copyOperator.size(); j++) {
if (order[i] == copyOperator.get(j)) {
if(order[i] == '+') {
copyNumbers.set(j, copyNumbers.get(j)+copyNumbers.get(j+1));
}
else if(order[i] =='-') {
copyNumbers.set(j, copyNumbers.get(j)-copyNumbers.get(j+1));
}
else if(order[i] == '*') {
copyNumbers.set(j, copyNumbers.get(j)*copyNumbers.get(j+1));
}
else {
copyNumbers.set(j, copyNumbers.get(j)/copyNumbers.get(j+1));
}
copyNumbers.remove(j+1);
copyOperator.remove(j);
j--;
}
}
}
if( Math.abs(copyNumbers.get(0)) > max) {
max = Math.abs(copyNumbers.get(0));
}
}
for (int i = 0; i < 4; i++) {
if (check[i] == false) {
check[i] = true;
if (i == 0) {
order[cnt] = '+';
} else if (i == 1) {
order[cnt] = '-';
} else if (i == 2) {
order[cnt] = '*';
} else if (i == 3) {
order[cnt] = '/';
}
permu(i + 1, cnt + 1, order, numbers, operator, check);
check[i] = false;
}
}
}
}
우선 가변적으로 연산을 하기위해 ArrayList로 숫자와 연산자를 받았습니다.
그 다음 순열을 통해 연산자 우선순위를 정하였고 순위에 따라 계산했습니다.