파이썬 알고리즘 - 일일 온도

문제

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

입력

T1 = [73,74,75,71,69,72,76,73]

출력

[1, 1, 4, 2, 1, 1, 0, 0]

작성한 코드 - 이중 for 문

def daily_temperatures1(T):
    t = [0]*len(T)
    count = 0
    # 이중 for 문
    for i in range(len(T)):
        count = 0
        for j in range(i+1,len(T),1):
            # 카운팅 하다가
            count += 1
            # 다음 온도가 클 때
            if T[i] < T[j]:
                t[i] = count
                break
    return t

리코드에서 시간 초과가 나왔다. - 스택을 이용해서 풀어 보자

책에 있는 코드

def daily_temperatures2(T):
    answer = [0]*len(T)

    stack = []
    # enumerate 인덱스와 값 동시에 접근 가능
    for i, cur in enumerate(T):
    	# 1. stack안에 값이 존재하는지
        # 2. 스택에 저장해둔 인덱스의 값과 현재 값을 비교
        while stack and T[stack[-1]] < cur:
            last = stack.pop()
            # 현재 인덱스에서 스택에서 가져온 인덱스를 빼면
            answer[last] = i - last
        stack.append(i)

    return answer

 

리코드에서 확인

https://leetcode.com/problems/daily-temperatures/

Daily Temperatures - LeetCode

 

회고

그나마 이해하기 쉬웠다.

스택으로 풀려고하니 조금 막히는 부분이 있어서 답을 좀 봤다 ㅠㅠ