문제 링크
내 풀이
일단 Combination 하는 방법부터 틀렸다. 순서가 정해져있으면 상관없는데 모든 경우의 수를 다를 수 있는 Combination을 제대로 구현하지 못했다는 점이 아쉽고 문제의 의도는 이해를 했지만 구현 능력 부족과 너무 복잡하게 구현을 할려고 한다는 점이 문제인 것 같다.
import java.util.*;
public class Client {
public static void main(String[] args) {
String exp = "100-200*300-500+20";
System.out.println(new Solution().solution(exp));
}
}
class Solution {
public static Stack<Stack<String>> orders = new Stack<>();
public static Set<String> tempOptions = new HashSet<>();
public static List<String> options = new ArrayList<>();
public long solution(String expression) {
ArrayDeque<String> q = new ArrayDeque<>();
StringBuilder temp = new StringBuilder(); // 헷갈린 문법
for (int i = 0; i < expression.length(); i++) {
if (!Character.isDigit(expression.charAt(i))) { // 헷갈린 문법
q.addLast(temp.toString()); // 피연산자 저장
String operand = String.valueOf(expression.charAt(i));
q.addLast(operand); // 연산자 저장
if (!tempOptions.contains(operand)) {
tempOptions.add(operand);
}
temp = new StringBuilder(); // 초기화
} else {
temp.append(expression.charAt(i)); // 헷갈린 문법
}
}
q.addLast(temp.toString()); // 마지막 문자열 저장
// 옵션 조합 생성
options = tempOptions.stream().toList(); // options HashSet -> List
for (int i = 0; i < tempOptions.size(); i++) {
combination(i, new Stack<>());
}
long result = calculate(q);
return result;
}
public Long calculate(ArrayDeque<String> q) {
Long max = 0L;
while (orders.size() > 0) {
ArrayDeque<String> tempQ = q;
Stack<String> curOrders = orders.pop();
while (curOrders.size() > 0) {
String curOp = curOrders.pop();
int qSize = q.size();
while (qSize > 0) {
Long f = Long.valueOf(tempQ.pollFirst());
String op = tempQ.pollFirst();
Long s = Long.valueOf(tempQ.pollFirst());
if (op.equals(curOp)) {
Long result = calculate(f, s, op);
tempQ.addFirst(String.valueOf(result));
} else {
tempQ.addLast(String.valueOf(f));
tempQ.addLast(op);
tempQ.addFirst(String.valueOf(s));
}
qSize--;
}
}
max = Collections.max(List.of(max, Long.valueOf(tempQ.pollFirst())));
}
return max;
}
public Long calculate(Long a, Long b, String operand) {
if (operand.equals("*")) {
return a * b;
} else if (operand.equals("+")) {
return a + b;
} else {
return a - b;
}
}
public void combination(int i, Stack<String> temp) {
if (temp.size() == tempOptions.size()) {
orders.add(temp);
return;
}
temp.add(options.get(i));
i++;
if (i >= options.size()) {
i = 0;
}
combination(i, temp);
}
}정답 풀이
인덱스를 좀 더 잘 다룰줄 알면 좋겠다.
import java.util.ArrayList;
class Solution {
public static long solution(String expression) {
long answer = Long.MIN_VALUE;
String op[][] = { { "+", "-", "*" }, { "+", "*", "-" }, { "-", "*", "+" },
{ "-", "+", "*" }, { "*", "-", "+" }, { "*", "+", "-" } };
ArrayList<String> list = new ArrayList<String>();
int start = 0;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) == '-' || expression.charAt(i) == '+' || expression.charAt(i) == '*') {
list.add(expression.substring(start, i)); // 연산자 앞 숫자 추가
list.add(expression.charAt(i) + ""); // 연산자 추가
start = i + 1;
}
}
list.add(expression.substring(start)); // 마지막 숫자 추가
for (int i = 0; i < op.length; i++) {
ArrayList<String> sub_list = new ArrayList<String>(list);
for (int k = 0; k < 3; k++) {
for (int j = 0; j < sub_list.size(); j++) {
if (op[i][k].equals(sub_list.get(j))) {
sub_list.set(j - 1, calc(sub_list.get(j - 1), sub_list.get(j), sub_list.get(j + 1)));
sub_list.remove(j);
sub_list.remove(j);
j--;
}
}
}
answer = Math.max(answer, Math.abs(Long.parseLong(sub_list.get(0))));
}
return answer;
}
private static String calc(String num1, String op, String num2) {
long n1 = Long.parseLong(num1);
long n2 = Long.parseLong(num2);
if (op.equals("+"))
return n1 + n2 + "";
else if (op.equals("-"))
return n1 - n2 + "";
return n1 * n2 + "";
}
}