이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
문제 정의
온도 리스트를 입력받아 각 온도가 더 높은 값을 만날 때까지의 걸린 시간 리스트 출력
책에서 구현된 코드
def dailyTemperatures(self, T: list[int]) -> list[int]:
answer = [0] * len(T)
stack = []
for i, cur in enumerate(T):
while stack and cur > T[stack[-1]]:
last = stack.pop()
answer[last] = i - last
stack.append(i)
return answer
기억해야할 기법
- [0] * len(T)
- 더 짧아서 깔끔해보임
- index와 list를 알 경우, stack에 indext만 push하면 값을 저장할 필요 없음
- 변하는 값, 축적된 값만 stack push하면 될 듯
내가 구현한 코드
def dailyTemperatures(temperatures: list[int]) -> list[int]:
stack = []
res = [0 for _ in range(len(temperatures))]
for idx, temp in enumerate(temperatures):
if not stack:
stack.append((idx, temp))
continue
while stack and stack[-1][1] < temp:
stk_idx, stk_temp = stack.pop()
res[stk_idx] = idx - stk_idx
stack.append((idx, temp))
while stack:
stk_idx, stk_temp = stack.pop()
res[stk_idx] = 0
return res
- if not stack 부분이 필요 없음
- 아래 while문 필요 없음
'책읽기' 카테고리의 다른 글
[파이썬 알고리즘 인터뷰][스택/큐] 스택을 이용한 큐 구현 (0) | 2021.07.23 |
---|---|
[파이썬 알고리즘 인터뷰][스택/큐] 큐를 이용한 스택 구현 (0) | 2021.07.23 |
[파이썬 알고리즘 인터뷰][스택/큐] 중복 문자 제거 (0) | 2021.07.23 |
[파이썬 알고리즘 인터뷰][스택/큐] 유효한 괄호 (0) | 2021.07.23 |
[파이썬 알고리즘 인터뷰] 9장 - 스택, 큐 (0) | 2021.07.23 |