문제
당신은 수식을 독특한 방식으로 계산해야 한다. 수식을 계산하는 방식은 다음과 같다.
- 수식에서 맨 앞의 연산자, 또는 맨 뒤의 연산자 먼저 계산한다. 단, 음수의 부호는 연산자로 취급하지 않는다.
- 곱셈, 나눗셈을 덧셈, 뺄셈보다 더 먼저 계산한다.
- 연산자의 우선순위가 같다면 해당 연산자를 계산했을 때 결과가 큰 것부터 계산한다.
- 계산했을 때 결과 값 또한 같다면 앞에 것을 먼저 계산한다.
예를 들어서 수식이 3 x 2 + 5 - 5 + 7으로 주어진다고 하면 다음과 같이 계산된다.
- 3 x 2와 5 + 7 중에서 계산 우선순위가 더 높은 x를 먼저 계산한다. 이후 계산식은 6 + 5 - 5 + 7이다.
- 앞뒤의 연산자가 같으므로 6 + 5와 5 + 7을 비교했을 때, 5 + 7이 더 크기 때문에 뒤에 있는 +를 먼저 계산한다. 이후 계산식은 6 + 5 - 12이다.
- 뺄셈과 덧셈의 우선순위가 같으므로 6 + 5와 5 - 12를 비교했을 때, 6 + 5가 더 크기 때문에 +를 먼저 계산한다. 이후 계산식은 11 - 12가 된다.
- 11 - 12를 계산하면 최종 결과 값은 -1이 된다.
수식은 반드시 수와 연산자가 번갈아 가면서 나온다. 마지막에 연산자가 있는 경우는 존재하지 않으며, 맨 앞을 제외하고 음수가 들어오는 경우도 존재하지 않는다. 즉, -1 - 1 같은 경우는 나올 수 있으나, 2 + -3 같은 경우는 존재하지 않는다고 가정해도 된다. 그리고 불필요한 0이 앞에 있을 수 있다. 즉, 001 + 0002 같은 수식이 나올 수 있다.
또한, 이 문제에서의 나눗셈은 C++에서 정수 간에 정의된 나눗셈으로 생각한다. 즉, 나누어지는 수가 양수면 나머지가 0 이상, 음수면 나머지가 0 이하로 처리가 되는 식으로 진행했을 때 나오는 몫을 계산하는 방식으로 이루어진다. 예를 들어, 3 / 2 = 1, (-3) / 2 = -1, 3 / (-2) = -1, (-3) / (-2) = 1로 계산된다.
이와 같은 계산 과정에 따라 주어진 식을 계산하시오.
입력
숫자, '+', '*', '-', '/'로만 이루어진 길이가 10^6 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 -2^63 이상 2^63 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다.
출력
주어진 식을 계산한 결과 값을 출력한다. 불필요한 0은 제거해야 한다.
풀이
핵심은 숫자 덱과 연산자 덱을 만들어 양끝 연산을 시뮬레이션하는 것이다. 먼저 문자열을 파싱해서 numbers, operators 두 덱에 넣는다.
이후 양끝 연산자의 우선순위를 비교한다. 우선순위가 높은 쪽을 먼저 계산하고, 같다면 실제로 양쪽을 한번 계산해 본 뒤 더 큰 값을 만드는 쪽을 선택한다. 그렇게 선택된 쪽의 숫자 두 개와 연산자 하나를 꺼내 계산 결과를 다시 같은 쪽에 넣는다.
연산자가 모두 사라질 때까지 반복하면 마지막 숫자가 정답이 된다.
파싱할 때 첫 글자가 -인 경우를 따로 처리하는 점도 중요하다. 맨 앞의 음수 부호를 일반 연산자로 보면 숫자와 연산자 분리가 틀어지기 때문에, 코드에서는 첫 문자가 -일 때 현재 숫자 문자열에 붙여서 시작한다.
또한 우선순위가 같은 경우에는 단순히 왼쪽부터 처리하지 않고, 양쪽 계산 결과를 실제로 비교해 더 큰 값을 택한다. 문제의 계산 규칙을 그대로 옮긴 시뮬레이션이라서, 덱 양끝을 동시에 다루는 구조가 잘 맞는다.
코드
import java.io.*;
import java.util.*;
public class Main {
static Deque<Long> numbers = new ArrayDeque<>();
static Deque<Character> operators = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
StringBuilder number = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
char cur = input.charAt(i);
if (i == 0 && cur == '-') {
number.append(cur);
continue;
}
if (Character.isDigit(cur)) {
number.append(cur);
} else {
numbers.offer(Long.parseLong(number.toString()));
number = new StringBuilder();
operators.offer(cur);
}
}
if (number.length() > 0)
numbers.offer(Long.parseLong(number.toString()));
System.out.println(solve());
}
static long solve() {
while (!operators.isEmpty()) {
char leftOperator = operators.peekFirst();
char rightOperator = operators.peekLast();
int leftDegree = getDegree(leftOperator);
int rightDegree = getDegree(rightOperator);
long left1 = numbers.pollFirst();
long left2 = numbers.peekFirst();
numbers.offerFirst(left1);
long right2 = numbers.pollLast();
long right1 = numbers.peekLast();
numbers.offerLast(right2);
if (leftDegree == rightDegree) {
long leftCal = calculate(leftOperator, left1, left2);
long rightCal = calculate(rightOperator, right1, right2);
if (leftCal >= rightCal) leftDegree++;
else rightDegree++;
}
if (leftDegree > rightDegree) {
long n1 = numbers.pollFirst();
long n2 = numbers.pollFirst();
numbers.offerFirst(calculate(leftOperator, n1, n2));
operators.pollFirst();
} else {
long n2 = numbers.pollLast();
long n1 = numbers.pollLast();
numbers.offerLast(calculate(rightOperator, n1, n2));
operators.pollLast();
}
}
return numbers.getFirst();
}
static int getDegree(char op) {
if (op == '*' || op == '/') return 2;
else return 1;
}
static long calculate(char op, long n1, long n2) {
if (op == '*') return n1 * n2;
else if (op == '/') return n1 / n2;
else if (op == '+') return n1 + n2;
else return n1 - n2;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
일반 계산기처럼 한쪽에서만 처리하는 게 아니라, 양끝을 동시에 보며 선택해야 해서 덱이 잘 어울린다. 파싱과 시뮬레이션을 정확히 나누는 게 중요하다.
