Algorithm[Daily Temperatures - LeetCode]

매일의 화씨 온도(T) 리스트를 입력받아서, 더 따뜻한 날짜를 위해서는 몇일을 더 기다려야 하는지를 출력하라.

입력
73 74 75 71 69 72 76 73
출력
[1, 1, 4, 2, 1, 1, 0, 0]

✏️ 문제풀이 (stack)

온도의 index를 stack에 계속 채우다가 더 높은 온도를 만났을 때 stack의 요소를 pop한다. pop한 index를 통해 ans 리스트를 수정한다.

temperatures = list(map(int,input().split()))
stack = []
ans = [0]*len(temperatures)

for ind, val in enumerate(temperatures):
    while stack and temperatures[stack[-1]] < val:
        ans_ind = stack.pop()
        ans[ans_ind] = ind - ans_ind
    stack.append(ind)
print(ans)

Time Complexity: O(n)