제출 코드
- 사용 알고리즘 :
순열
순열로 나올 수 있는 연산자 우선순위에 대한 모든 경우의 수를 구하고, 각 경우마다 우선순위대로 연산을 진행하였다.
우선순위대로 연산하면서, 이전 값은 지우고 연산된 결과를 저장하는 방식에서 배열을 사용했다.
다시 생각해보니 배열이 아닌 리스트로 구현했다면, 연산이 끝난 결과를을 제거하면서 자연스레 인덱스 정리도 되어 더 간단했을 문제였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.*;
class Solution {
String[] pm = {"+", "-", "*"}; //43 45 42
String[] exp, exp_copy;
int[] key = new int[3];
boolean[] visit = new boolean[3];
long max = Long.MIN_VALUE;
// 연산자 우선순위의 모든 경우의 수 구하기
void perm(int n){
if(n==3) {
for(int i=0; i<exp.length; i++) exp_copy[i] = exp[i];
max = Math.max(Math.abs(go()), max);
return;
}
for(int i=0; i<3; i++){
if(!visit[i]) {
visit[i] = true;
key[n] = i;
perm(n+1);
visit[i] = false;
}
}
}
// 주어진 우선순위대로 연산 진행
long go(){
for(int k : key){
for(int i=0; i<exp_copy.length; i++){
if(exp_copy[i].equals(pm[k])){ //이번 턴에 계산할 연산자를 찾으면 계산수행
int start=i, end=i;
long left=-1, right=-1;
while(true){ // 연산자의 왼쪽 수 찾기
--start;
if(exp_copy[start].length() == 0) continue;
left = Long.parseLong(exp_copy[start]);
exp_copy[start] = "";
break;
}
while(true){ // 연산자의 오른쪽 수 찾기
++end;
if(exp_copy[end].length() == 0) continue;
right = Long.parseLong(exp_copy[end]);
exp_copy[end] = "";
break;
}
exp_copy[i] = calc(left, right, exp_copy[i]) + "";
}
}
}
for(String s : exp_copy){ // 최종 결과 반환
if(s.length()!=0) {
return Long.parseLong(s);
}
}
return -1;
}
// 주어진 연산자로 계산
long calc(long a, long b, String s){
switch(s){
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
}
return -1;
}
public long solution(String expression) {
char[] tmp = expression.toCharArray();
String str = "";
List<String> strs = new ArrayList<String>();
for(char c : tmp){
if(c=='+' || c=='-' || c=='*') {
strs.add(str);
strs.add(c+"");
str="";
}else str += c;
}
strs.add(str);
exp = strs.toArray(new String[strs.size()]);
exp_copy = new String[exp.length];
perm(0);
long answer = max;
return answer;
}
}