⭐️ LeetCode 알고리즘 풀이 (with Python)
# Min Stack
[Quetion]
📌 접근법
[문제 이해]
- Stack 자료구조의 클래스 구현
- Push ,Pop 기능과 최소값을 반환하는 getMin() 기능 구현
- 가장 최근 Push된 값을 반환하는 top()기능 구현
Stack이 가득 찬 경우와 비어있는 경우의 요구사항이 별도로 없어서 제외하고 생각했다.
그리고 최소값은 min()함수, top 기능은 top 변수를 활용하여 구현해보았다.
💻 구현
class MinStack(object):
def __init__(self):
self.stack=[]
# stack 내부 포인터 변수
self.topnum = -1
def push(self, val):
# append() : list 마지막 인덱스에 값 추가
self.stack.append(val)
self.topnum += 1
def pop(self):
# pop() : 리스트에서 마지막 값을 삭제 후 반환
self.stack.pop()
self.topnum -= 1
def top(self):
# topnum : 항상 stack 최상위를 가르키고 있음
return self.stack[self.topnum]
def getMin(self):
# stack 내부에서 가장 작은 값 반환
return min(self.stack)Runtime: 348ms | Memory: 16.9MB
LeetCode 코드 중 Runtime 16%, Memory 76% 해당하는 결과
📝 Min Stack 회고
- LIFO (후입선출 : 가장 마지막에 들어온 값이 먼저 나감)이 핵심인 Stack의 기본을 구현하는 문제였다.
- append()와 pop(), min()과 같은 Python 함수를 활용하여 어렵지 않게 구현했는데, Runtime이 많이 느리게 나와서 개선이 필요하다고 생각했다.
- min() 함수로 최소값을 반환하는 것이 아니라 최소값을 담는 스택을 더 추가하면 Runtime을 개선할 수 있을 것 같다.
# 개선 후
class MinStack:
def __init__(self):
self.stack=[]
self.topnum = -1
# 최소값을 담는 min stack 추가
self.minnum=[]
def push(self, val):
# 처음 push 할 때는 minnum도 같이 push
if len(self.stack)==0:
self.stack.append(val)
self.topnum += 1
self.minnum.append(val)
else:
self.stack.append(val)
self.topnum += 1
# push 값이 최소값 보다 작으면 min stack에 push
# 아니면 현재 최소값을 다시 push
if self.minnum[-1] > val:
self.minnum.append(val)
else:
self.minnum.append(self.minnum[-1])
def pop(self):
# 최소값과 현재 스택을 같이 삭제
self.stack.pop()
self.minnum.pop()
self.topnum -= 1
def top(self):
return self.stack[self.topnum]
def getMin(self):
# min stack의 최상단 값 반환
return self.minnum[-1]Runtime: 348ms ---> 53ms
Memory: 16.9MB ---> 20.49MB
코드는 조금 더 복잡해지고, Memory 사용량이 조금 더 증가 했지만 Runtime은 약 1/7로 줄어들었다.
min() 함수는 시간복잡도 O(n)을 가지지만, 직접 구현한 코드는 시간복잡도 O(1)이기 때문에 확실한 개선 효과를 얻은 것이다. 여기서 만약 개선한다면 최소값 스택을 정수형의 변수로 변경하여 Memory 사용량을 줄여 볼 수 있을것 같다.
# Evaluate Reverse Polish Notation
[Quetion]
📌 접근법
[문제 이해]
- 후위 표현식을 중위 표현식으로 변경
- +, -, *, / 연산자만 사용
중위 표현식 -> 후위 표현식의 방법은 다음과 같다.
- 피연산자가 나오면 스택에 Push
- 연산자가 나오면 스택에서 피연산자를 Pop하고 연산 수행 결과를 다시 스택에 Push
- 표현식의 끝까지 반복 후, 스택의 최상위 값이 최종 결과 값
이를 응용하여 다음과 같이 접근해보았다.
- 피연산자가 나오면 스택에 Push
- 연산자 별로 케이스를 분기하고, 해당 연산자가 나오면 스택에 쌓인 피연산자의 개수를 세고 2개 이상이면,
- 스택에서 Pop 연산을 두번 진행 후 Pop으로 반환된 값끼리 연산 진행 후 다시 스택에 Push
💻 구현
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
# 피연산자를 담을 stack 생성
stack=[]
# 연산자 리스트
oper = ['+','-','*','/']
for i in tokens:
if i == oper[0]:
if len(stack) >= 2:
stack.append(stack.pop() + stack.pop())
elif i == oper[1]:
if len(stack) >= 2:
a,b = stack.pop(), stack.pop()
stack.append(b-a)
elif i == oper[2]:
if len(stack) >= 2:
stack.append(stack.pop() * stack.pop())
elif i == oper[3]:
if len(stack) >= 2:
a,b = stack.pop(), stack.pop()
stack.append(int(b / a))
else:
stack.append(int(i))
return stack[0]Runtime: 75ms | Memory: 16.9MB
LeetCode 코드 중 Runtime 67%, Memory 14% 해당하는 결과
📝 Evaluate Reverse Polish Notation 회고
- Memory의 사용량이 많고, 스택에서 피연산자의 개수를 확인하는 조건문이 반복되었기 때문에 연산자 리스트를 제거하고 반복되는 조건문을 제거한다면 Memory 사용량을 개선할 수 있을 것 같다.
# 개선 후
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack=[]
for i in tokens:
# in 연산자로 4개의 연산자 확인
if i not in '+-*/':
stack.append(int(i))
# 피연산자 개수 확인하는 조건문 제거
else:
if i == '+':
stack.append(stack.pop() + stack.pop())
elif i == '-':
a,b = stack.pop(), stack.pop()
stack.append(b-a)
elif i == '*':
stack.append(stack.pop() * stack.pop())
else:
a,b = stack.pop(), stack.pop()
stack.append(int(b / a))
return stack[0]Runtime: 75ms ---> 70ms
Memory: 16.9MB ---> 16MB
기존 연산자 리스트를 제거하고 in 연산자로 피연산자인지 확인할 수 있게 변경했다. 또한 기존에는 가장 마지막에 실행되었던 피연산자를 스택에 Push하던 연산을 가장 먼저할 수 있게 되었다.
스택은 순서가 존재하는 자료구조이기 때문에 후위 표현식을 중위 표현식으로 변경할 때도 순서가 있고, 결론적으로 스택에 있는 피연산자의 개수는 확인할 필요가 없던 것이었다.
수치로는 큰 변화가 없지만 Runtime, Memory 각각 85%, 82%에 해당하는 코드로 괜찮은 결과를 얻었고, 불필요한 항목만 제거했을 뿐인데 개선의 효과가 나타난 것을 확인할 수 있었다.
# Two Sum
[Quetion]
📌 접근법
[문제 이해]
- 리스트에서 두 정수의 합이 target에 해당하는 경우, 해당 정수들의 인덱스를 반환
- 동일한 인덱스에 해당하는 정수는 재사용 불가
enumerate()를 활용하여 무작정 구현해보았다.
💡enumerate()는 인덱스와 값을 동시에 반환한다.
💻 구현
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i, val in enumerate(nums):
for j, val2 in enumerate(nums, start=0):
if i == j:
continue
if val + val2 == target:
return [i, j]Runtime: 5316ms | Memory: 17.1MB
LeetCode 코드 중 Runtime 6%, Memory 75% 해당하는 결과
📝 Two Sum 회고
- 중복 for문을 사용하여 시간복잡도가 O(n^2)에 해당하는 탓에 Runtime이 상당히 느리다.
- 중복 for문을 사용하지 않고 python의 dictionary 자료구조를 활용하면 시간복잡도를 O(n)으로 개선가능 할 것이다.
# 개선 후
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_dict = {}
for i, val in enumerate(nums):
# 리스트 내 첫번째 값 + ? = target에서 ?값
minus = target - val
# 만약 target이 되기 위한 나머지 하나의 정수가 dict에 없으면
# target에서 리스트 요소를 뺀 값을 key로 지정하고 인덱스를 저장
if minus not in nums_dict:
nums_dict[val] = i
# 있으면 인덱스와 dict에 있는 target이 되기 위한 나머지 정수 값의 인덱스 반환
else:
return [i, nums_dict[minus]]Runtime: 5316ms ---> 61ms
Memory: 17.1MB ---> 17.6MB
수정된 코드의 주석만 보면 왜 이렇게 코드가 구성된 것인지 헷갈릴 수 있다.
target에서 뺀 정수 즉 target이 되기 위한 나머지 수가 dict에 저장되어 있으면 그 값에 해당하는 인덱스를 반환하는 코드이다. {key : value} 형태의 해쉬 테이블 자료구조에서 아이디어를 얻었다.
결과적으로 무작정 대입하여 풀었을 때 보다 비교가 안될 정도의 Runtime 개선을 할 수 있었다.
해쉬 테이블 자료구조를 활용할 때 인덱스와 값을 동시에 알 수 있는 enumerte()가 유용하다는 것을 깨달았다.
