[LeetCode] - 일일온도(파이썬)

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

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

Daily Temperatures - LeetCode

▶ 입력 

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

▶ 출력

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

---

풀이)

 

먼저, 문제를 이해해보자. 

 

73도인 첫째 날 다음에 둘째 날이 74도 이므로 하루(1일)만 기다리면 된다. 75도인 셋째 날은 더 따뜻해지기 위해서 일곱째 날 까지 기다려야 하므로 4일을 기다려야 한다. 일곱째 날과 여덟째 날은 더 이상 따뜻해지는 날이 없으므로 0일이 된다.

 

이를 구하기 위해서 아래와 같은 순서대로 풀이할 수 있다. 

1. enumerate를 이용하여 특정 날짜의 인덱스와 온도를 기억한다. 
2. 온도리스트의 인덱스를 스택에 쌓아두면서 
   1. 만일 현재 온도에 쌓아둔 마지막 날의 온도보다 높다면 
   2. stack을 pop 한다
   3. 정답에 현재 인덱스와 pop한 인덱스의 차이를 저장한다

i	0	1	2	3	4	5	6	7
Temp	73	74	75	71	69	72	76	73
Stack	[0]	[1]	[2]	[2,3]	[2,3,4]	[2,5]	[6]	[6,7]
Last	-	0	1	-	-	4→3	5→2	-
answer	1-0 = 1	2-1 =1	6-2 =4	5-3 = 2	5-4 = 1	6-5 = 1	0	0

 

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        
        answer = [0] * len(temperatures)
        stack = []

        for i , temp in enumerate(temperatures) :
			
            while stack and temperatures[stack[-1]] < temp :
                last = stack.pop()
                answer[last] = i - last 

            stack.append(i)
        
        return answer

 

---

유사한 문제 - 프로그래머스 : 주식가격 

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

문제) 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지 return 하도록 soution 함수를 완성하세요. 

 

풀이)  

def solution(prices):
	answer = [0] * len(prices) 
    stack = [] 
    
    for idx, price in enumerate(prices) :
    	
        while stack and price < prices[stack[-1]] :
        	last = stack.pop()
            answer[last] = idx - last 
       
       stack.append(idx) 
  	   if answer[idx] == 0 :
       	answer[idx] = len(prices) - idx - 1 
        
    return answer