[파이썬 알고리즘 인터뷰][스택/큐] 일일 온도

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

온도 리스트를 입력받아 각 온도가 더 높은 값을 만날 때까지의 걸린 시간 리스트 출력

책에서 구현된 코드

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문 필요 없음