프로그래머스_수식 최대화
2022.01.28
문제
- 3가지 연산자(+, -, *)로 이루어져있다.
- 각 연산자는 우선순위를 정할 수 있다.
- 우선순위에 맞게 수식을 계산하여 최대값을 구한다.
- 계산값은 절대값으로 계산한다.
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420접근 방법
- 먼저 입력받은 문자열을 split 해서 숫자와 연산자를 구분해야한다. List 자료구조를 통해서 숫자, 연산자를 담았다. 그리고 숫자는 연산 할 때 int 범위를 넘어 갈 수 있어서 long 형식으로 캐스팅 처리를 해야한다. 그래서 처음부터 long형으로 입력 받아 계산을 하고자 했다.
- 연산자 우선순위를 정해야 한다. 모든 경우를 해봐야 하기 때문에 3중 for문을 사용하여 각 연산자의 우선순위를 처리했다. 그리고 연산자의 우선순위는 Map을 통해 갱신하여 관리했다.
-
이제는 정해진 우선순위를 바탕으로 수식을 계산해야한다. 이 부분에서 처음에 접근을 잘못해서 시간이 오래걸렸다.
- 처음에는 i번째 연산자의 우선순위와 (i-1)번 연산자의 우선순위를 비교해서 i번째 연산자가 더 크면 수식을 계산하는 방법을 생각했다. 그런데 해당 방법은 잘못된 방법이었다. 가장 큰 연산자가 아니고 2번째로 큰 수식도 계산을 하기 때문이다. 예를들어) 100 - 200 * 300 + 1000 * 20 수식과 * > + > - 우선순위가 있을 때, (200 * 300) 연산을 수행하고 (1000 * 20) 연산을 수행해야 하는데, 내가 생각한 방법대로 진행하면 (200 * 300) 연산을 수행한 뒤, - 연산자와 + 연산자를 비교하고 +연산자가 우선순위가 높기 때문에 (60000 + 1000) 연산을 수행하게 된다. 따라서 해당 방법으로는 진행할 수 없다.
- 그래서 계산할 때마다 가장 큰 연산자를 찾고, 해당 계산을 처리하는 방법으로 해야한다. 가장 큰 연산자의 위치 i를 구하고, i번 숫자와 i+1번 숫자를 해당 연산자로 계산을 한다. 그리고 계산된 숫자를 list의 맨 앞에 갱신해준다. 그 다음, 계산이 완료된 숫자와 연산자는 제거한다. 이러한 방법으로 모든 연산자를 사용할 때까지 진행하고 최대값을 갱신하면 된다.
소스 코드
import java.util.*;
class Solution {
static List<Long> numbers = new ArrayList<>();
static List<Character> operations = new ArrayList<>();
static Set<Character> validOperation = new HashSet<>(Arrays.asList('+', '-', '*'));
static Map<Character, Integer> operationPoint = new HashMap<>();
public long solution(String expression) {
long answer = 0L;
splitExpression(expression);
for (int plus = 0; plus < 3; plus++) {
for (int minus = 0; minus < 3; minus++) {
if (minus == plus)
continue;
for (int multiply = 0; multiply < 3; multiply++) {
if (multiply == plus || multiply == minus)
continue;
setOperationPoint(plus, minus, multiply);
answer = Math.max(answer, Math.abs(getMaxTotal()));
}
}
}
return answer;
}
private long getMaxTotal() {
// 연산자는 없고 숫자만 입력된 경우
if (operations.size() == 0) {
return numbers.get(0);
}
List<Long> numberContainer = new ArrayList<>();
List<Character> operationContainer = new ArrayList<>();
for (int i = 0; i < operations.size(); i++) {
operationContainer.add(operations.get(i));
numberContainer.add(numbers.get(i));
}
numberContainer.add(numbers.get(operationContainer.size()));
while (!operationContainer.isEmpty()) {
int maxPointIndex = findMaxPointIndex(operationContainer);
long numberA = numberContainer.get(maxPointIndex);
long numberB = numberContainer.get(maxPointIndex + 1);
char operation = operationContainer.get(maxPointIndex);
long total = calculate(numberA, numberB, operation);
numberContainer.set(maxPointIndex, total);
numberContainer.remove(maxPointIndex + 1);
operationContainer.remove(maxPointIndex);
}
return numberContainer.get(0);
}
private int findMaxPointIndex(List<Character> operationContainer) {
int point = 0;
int index = 0;
for (int i = 0; i < operationContainer.size(); i++) {
int nextPoint = operationPoint.get(operationContainer.get(i));
if (nextPoint > point) {
point = nextPoint;
index = i;
}
}
return index;
}
private long calculate(long numberA, long numberB, char operation) {
if (operation == '+') {
return numberA + numberB;
}
if (operation == '-') {
return numberA - numberB;
}
return numberA * numberB;
}
private void setOperationPoint(int plus, int minus, int multiply) {
operationPoint.put('+', plus);
operationPoint.put('-', minus);
operationPoint.put('*', multiply);
}
private void splitExpression(String expression) {
int start = 0;
char[] expressions = expression.toCharArray();
for (int i = 0; i < expression.length(); i++) {
if (validOperation.contains(expressions[i])) {
long number = Long.parseLong(expression.substring(start, i));
start = i + 1;
operations.add(expressions[i]);
numbers.add(number);
}
}
long number = Long.parseLong(expression.substring(start));
numbers.add(number);
}
}