문제
1차 풀이 (2020.11.23)
시작
주어진 expression을 파싱해서 숫자와 연산자를 저장하고,
연산자들 계산 순서를 모두 구하고, 각 경우의 수마다 계산하여 최댓값을 구해야 했다.
연산자들 계산 순서 순열을 구해야 하는데, 코드를 직접 짤 시간은 없어서 검색해서 이해가 가는 코드를 보고 변형해서 썼다.
최댓값을 구할 때 연산자 좌우의 수를 가지고 계산을 해야 한다는 생각에, List가 아닌 Map에다가 연산자와 그 연산자의 index를 같이 저장해서 구현을 해보았다. 하지만 계산한 결과 값들을 가지고 또 계산을 할 때는 그 index 값이 무의미해지기 때문에 List에서 element들을 빼가면서 연산을 하는 방식으로 구현을 했더니 성공할 수 있었다.
메소드
doPermutationForOperandOrders()
operand 배열 순열 경우의 수를 구하는 메소드다. recursion을 이용해서 구현했다.
start index를 하나씩 밀면서 메소드를 호출하고, 종료 조건에 걸리면 순열을 저장하는 전역 변수에 저장한다.
calcMaxResult()
최대 결과값을 구하기 위해 순열 경우의 수마다 result 값을 구하고, 최대값을 업데이트하는 메소드다.
calcResultWithGivenOrder()
순열 경우의 수가 주어지면 그 순서에 맞도록 연산자를 적용해서 result 값을 구하는 메소드다.
최우선 순위의 연산자부터 마지막 연산자까지 순서대로 계산하기 위해서, 차례대로 calcOnTargetOperand()를 호출하여 그 연산자만 계산한다.
calcOnTargetOperand()
tmpOperands를 탐색하면서 targetOp와 같으면 계산을 수행한다. 계산 수행 후 계산 완료된 부분을 처리하기 위해, 해당 연산자를 list에서 삭제한다.
calc()
연산자 좌우 숫자를 가지고 계산을 한다. 추후 계산에 결과값을 활용해야 하기 때문에, tmpNums에서 숫자 하나만 결과값으로 저장한다.
실수
- 결과를 저장하는 값에는 long으로 잘 선언했는데, 결과를 임시저장하는 데에도 쓰이는
tmpNums는 int로 선언해서 테스트케이스를 일부 통과하지 못했다. 범위를 꼼꼼히 보자.
새로 배운 것
Permutation & Combination이 코딩테스트를 치기 위한 베이스..라는 것을 알게 되었다. 그걸 못하는 나는 기본이 없는 사람이라는 뜻..!
일단 recursion으로 구현해놨긴 한데, 더 효율적인 방법이 있는 것 같아서 더 공부하고 싶어졌다. 종강하면 알고리즘 기초를 탄탄히 공부하고 싶다.
코드
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Solution {
private static List<Long> nums = new ArrayList<>();
private static List<Character> operands = new ArrayList<>();
private static List<char[]> operandOrders = new ArrayList<>();
private static List<Long> tmpNums;
private static List<Character> tmpOperands;
private static long answer;
public long solution(String expression) {
parseExpression(expression);
calcMaxResult();
return answer;
}
private void parseExpression(String expression) {
seperateNumsAndOperands(expression);
char[] tmpOperandType = checkOperandTypes();
doPermutationForOperandOrders(tmpOperandType, 0);
}
private void seperateNumsAndOperands(String expression) {
StringBuilder sb = new StringBuilder();
for (char ch : expression.toCharArray()) {
if (ch == '+' || ch == '-' || ch == '*') {
nums.add(Long.parseLong(sb.toString()));
operands.add(ch);
sb = new StringBuilder();
} else
sb.append(ch);
}
nums.add(Long.parseLong(sb.toString()));
}
private char[] checkOperandTypes() {
Set<Character> operandTypeSet = new HashSet<>(operands);
char[] operandType = new char[operandTypeSet.size()];
int i = 0;
for (Character op : operandTypeSet) {
operandType[i++] = op;
}
return operandType;
}
private void doPermutationForOperandOrders(char[] arr, int start) {
int length = arr.length;
if (start == length - 1) {
operandOrders.add(arr.clone());
return;
}
for (int i = start; i < length; i++) {
swap(arr, start, i);
doPermutationForOperandOrders(arr, start + 1);
swap(arr, start, i);
}
}
private void swap(char[] arr, int n1, int n2) {
char temp = arr[n1];
arr[n1] = arr[n2];
arr[n2] = temp;
}
private void calcMaxResult() {
for (char[] order : operandOrders) {
long result = calcResultWithGivenOrder(order);
updateAnswer(result);
}
}
private long calcResultWithGivenOrder(char[] order) {
tmpNums = new ArrayList<>(nums);
tmpOperands = new ArrayList<>(operands);
for (char targetOp : order) {
calcOnTargetOperand(targetOp);
}
return tmpNums.get(0);
}
private void calcOnTargetOperand(char targetOp) {
int length = tmpOperands.size();
for (int i = 0; i < length; i++) {
char op = tmpOperands.get(i);
if (op == targetOp) {
calc(i, op);
tmpOperands.remove(i--);
length--;
}
}
}
private void calc(int index, char op) {
long left = tmpNums.get(index);
long right = tmpNums.get(index + 1);
long result = switch (op) {
case '*' -> left * right;
case '+' -> left + right;
case '-' -> left - right;
default -> 0;
};
tmpNums.set(index, result);
tmpNums.remove(index + 1);
}
private void updateAnswer(long result) {
long absResult = Math.abs(result);
if (absResult > answer) answer = absResult;
}
}참고
2차 풀이 (2021.05.03)
설명
저번에 풀 때는 순열을 못 구해서 이것도 검색을 해서 풀었었구나..! 그래도 한 단계 정도는 성장했나보다 아자!^^..
순열은 DFS로 구했고, 각 연산순위 경우의 수마다 calcResult()에서 계산을 했다. calcResult()는 저번과는 다르게 Queue 2개를 활용해서, 순서대로 한 연산자씩 다 계산하는 방식으로 구현했다.
코드
import java.util.*;
class Solution {
private static final String MUL = "*";
private static final String ADD = "+";
private static final String SUB = "-";
private static final List<String> operands = new ArrayList<>();
private long max;
public long solution(String expression) {
initOperands();
Queue<String> queue = parseExpression(expression);
calcMax(queue);
return max;
}
private void initOperands() {
operands.add(MUL);
operands.add(ADD);
operands.add(SUB);
}
private Queue<String> parseExpression(String expression) {
Queue<String> queue = new LinkedList<>();
StringBuilder num = new StringBuilder();
for (char current : expression.toCharArray()) {
if (current >= '0' && current <= '9')
num.append(current);
else {
queue.offer(num.toString());
queue.offer(String.valueOf(current));
num = new StringBuilder();
}
}
queue.offer(num.toString());
return queue;
}
private void calcMax(Queue<String> queue) {
String[] current = new String[3];
boolean[] visited = new boolean[3];
permutation(current, visited, 0, 3, queue);
}
private void permutation(String[] current, boolean[] visited, int depth, int target, Queue<String> queue) {
if (depth == target) {
Queue<String> tmp = new LinkedList<>(queue);
long result = calcResult(tmp, current);
max = Math.max(max, result);
return;
}
for (int i = 0; i < 3; i++) {
if (!visited[i]) {
visited[i] = true;
current[depth] = operands.get(i);
permutation(current, visited, depth + 1, target, queue);
current[depth] = null;
visited[i] = false;
}
}
}
private long calcResult(Queue<String> queue, String[] calcOrder) {
Queue<String> result = new LinkedList<>();
Queue<String> tmp = new LinkedList<>(queue);
for (String targetOperand : calcOrder) {
String before = "", operand = "", current = "";
while (!tmp.isEmpty()) {
current = tmp.poll();
if (operands.contains(current)) {
if (current.equals(targetOperand))
operand = current;
else {
result.offer(before);
result.offer(current);
before = "";
}
} else if (before.isBlank())
before = current;
else {
before = calc(before, operand, current);
operand = "";
}
}
result.offer(before);
tmp.addAll(result);
result = new LinkedList<>();
}
return Math.abs(Long.parseLong(tmp.poll()));
}
private String calc(String before, String operand, String current) {
long left = Long.parseLong(before);
long right = Long.parseLong(current);
switch (operand) {
case MUL:
return String.valueOf(left * right);
case ADD:
return String.valueOf(left + right);
case SUB:
return String.valueOf(left - right);
}
return null;
}
}