참고
문제해설
NOTE
•
입력 값 ⇒ 후위 표기식 산술
•
출력 값 ⇒ 산술결과
문제 로직고민
NOTE
•
Stack에 정수값들을 넣으면서, 연산자를 만나면 꺼내서 계산한다.
◦
연산자를 만났는데, 아직 아무런값도 계산되지 않았다 ⇒ 정수 2개를 스택에서 꺼내 연산자 계산
◦
연산자를 만났는데, 이전에 계산된 값이 있다 ⇒ 정수 1개를 스택에서 꺼내 이전에 계산한 값과 연산자 계산
◦
후위 표기식의 경우, 연산자를 만났을때 정수값이 없는 경우가 없다고 판단했다.
•
초기 계산값을 어떻게 설정해야하는가?
◦
0 ⇒ 계산 도중 0이 나올 확률이 존재한다.
◦
Integer.MIN_VALUE ⇒ 각 숫자의 범위가 -200~200이고, 길이가 4만이므로, 넉넉하게 잡아 최소 -800만이라 가정할때 적절한것 같다.
•
정수의 순서가 올바르지 않다.
◦
위의 과정대로 코드를 짜본결과 연산의 순서는 맞으나, 정수의 위치가 올바르지 않았다.
▪
ex) 6 / -132가 나와야하는데, -132 / 6이 되어버림
◦
이는 연산자가 연속으로 나올때 이러한 패턴이 나온다는걸 발견했다.
▪
연산자가 연속으로 등장하지 않는다. ⇒ 기존의 계산값 , 연산자, 정수
▪
연산자가 연속으로 등장한다. ⇒ 정수, 연산자, 기존의 계산값
◦
정수의 순서가 중요한 -, / 연산에 코드를 추가로 작성해준다.
•
위의 대전제가 틀렸다.
◦
연산자를 통한 계산에서 이전에 사용했던 값을 무조건 사용하는게 아니다!
◦
ex) (1+2) - (4+5)의 경우 1 2 + 4 5 + -로 표현되기 때문
▪
1+2의 계산값인 3은 4와 5의 연산에서 사용되지 않는다.
◦
즉 합쳐진 값을 Stack에 남겨두고, 가장 최근값 2개를 통한 연산을 진행하는 것!
작성코드
NOTE
class Solution {
public int evalRPN(String[] tokens) {
int[] stack = new int[40000];
int result = 0;
int idx = 0;
for(String s : tokens){
if(s.equals("+")){
result = stack[idx-2] + stack[idx-1];
stack[idx-2] = result;
idx--;
}
else if(s.equals("-")){
result = stack[idx-2] - stack[idx-1];
stack[idx-2] = result;
idx--;
}
else if(s.equals("*")){
result = stack[idx-2] * stack[idx-1];
stack[idx-2] = result;
idx--;
}
else if(s.equals("/")){
result = stack[idx-2] / stack[idx-1];
stack[idx-2] = result;
idx--;
}
else stack[idx++] = Integer.parseInt(s);
}
return stack[idx-1];
}
}
Java
복사
정답코드
NOTE
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int first, second;
for (String curr : tokens) {
if (curr.equals("+")) {
second = stack.pop();
first = stack.pop();
stack.add(first + second);
} else if (curr.equals("-")) {
second = stack.pop();
first = stack.pop();
stack.add(first - second);
} else if (curr.equals("*")) {
second = stack.pop();
first = stack.pop();
stack.add(first * second);
} else if (curr.equals("/")) {
second = stack.pop();
first = stack.pop();
stack.add(first / second);
} else {
stack.add(Integer.parseInt(curr));
}
}
return stack.pop();
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
이전문제에서 메모리를 많이 쓰는 이유가 라이브러리 자료구조를 사용해서 그런줄 알았는데, 메모리가 가장 적은 코드가 Stack자체를 쓴 코드라 신기했다.
•
로직 자체는 내가 작성한 코드와 동일한것 같다.
class Solution {
int pointer;
public int evalRPN(String[] tokens) {
if (tokens == null) return 0;
if (tokens.length == 1) return Integer.parseInt(tokens[0]);
pointer = tokens.length - 1;
return dfs(tokens);
}
public int dfs(String[] tokens){
String s = tokens[pointer--];
if (!(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/"))) return Integer.parseInt(s);
int right = dfs(tokens);
int left = dfs(tokens);
int result = 0;
if (s.equals("+")) return left + right;
else if (s.equals("-")) return left - right;
else if (s.equals("*")) return left * right;
else if (s.equals("/")) return left / right;
return result;
}
}
Java
복사
실행시간이 가장 빠른 코드
•
dfs를 통한 재귀함수를 사용했는데, 이게 실행시간과 연관이 있는건지 잘 모르겠다.