๐ค ๋ฌธ์ ์ดํด
tokens์ ์ฃผ์ด์ง ๋ฐฐ์ด์ stack์ ์ด์ฉํ์ฌ ๊ณ์ฐํ๋ผ (์์๋ฅผ ๋ณด๋ฉด์ ์ดํดํ ์ ์์์ด)
๐ค EX
data example 1
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
data example 2
Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
data example 3
Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
๐ค ์์ฌ ์ฝ๋
let stack =[] ----> stack์ผ๋ก ์ฌ์ฉํ ๋ฐฐ์ด ์ ์ธ
for(const element of tokens){
if(์ซ์์ธ์ง ํ์ธ){
stack.push(Number(element))
}else{
let num1=stack.pop()
let num2 = stack.pop()
switch(element){
case "+":
stack.push(num1+num2)
break;
..... ์๋ต......
}
}
return stack.pop()
๐ค ํด๊ฒฐํ ์ฝ๋ : O(n)
์์ฌ ์ฝ๋ ๊ทธ๋๋ก ๊ตฌํํ์๋๋ ๋๋๊ธฐํ ๋์ ๋ฌธ์ ๊ฐ ์๊ฒผ๊ณ console.log()๋ฅผ ์ฐ์ด ๊ณ์ฐ์์๊ฐ num1๊ณผ num2๋ฅผ ๊ณ์ฐ ์์น๋ฅผ ๋ฐ๊ฟ ์ค์ผํด์ ์์ ํ๋ ํด๊ฒฐํ ์ ์์๋ค.
var evalRPN = function(tokens) {
let stack = []
for (const element of tokens) {
if(!isNaN(element)){
stack.push(Number(element))
}else{
const num1 = stack.pop()
const num2 = stack.pop()
switch(element) {
case "+":
stack.push(num2+num1)
break;
case "-":
stack.push(num2-num1)
break;
case "/":
stack.push(Math.trunc(num2/num1))
break;
case "*":
stack.push(num2*num1)
break;
}
}
}
return stack.pop()
}
๐ค ๋ค๋ฅธ ํ์ด๋ฐฉ๋ฒ
๋ค๋ค ๋น์ทํ๊ฒ ํ์๋ค. switch case๊ฐ ์๋ if else๋ ์์๊ตฌ ๊ธฐ์ด์ ์ธ ๋ก์ง์ ์ ๊ตฌํํ ๊ฒ ๊ฐ๋ค.
https://leetcode.com/problems/evaluate-reverse-polish-notation/
'์ฝํ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] Linked list : Leetcode - 2. Add Two Numbers : ํด๊ฒฐ์ค (0) | 2023.08.28 |
---|---|
[์๋ฃ๊ตฌ์กฐ] Linked list - 2 (0) | 2023.08.28 |
LeetCode Top Interview 150 - 209. Minimum Size Subarray Sum (0) | 2023.08.27 |
LeetCode Top Interview 150 - 3. Longest Substring Without Repeating Characters (0) | 2023.08.26 |
LeetCode Top Interview 150 - 167. Two Sum II - Input Array Is Sorted (0) | 2023.08.25 |