풀이) 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서 며칠을 더 기다려야 하는지 출력하라.
https://leetcode.com/problems/daily-temperatures/
▶ 입력
T = [ 73, 74, 75, 71, 69, 72, 76, 73 ]
▶ 출력
[ 1, 1, 4, 2, 1, 1, 0, 0 ]
풀이)
먼저, 문제를 이해해보자.
73도인 첫째 날 다음에 둘째 날이 74도 이므로 하루(1일)만 기다리면 된다. 75도인 셋째 날은 더 따뜻해지기 위해서 일곱째 날 까지 기다려야 하므로 4일을 기다려야 한다. 일곱째 날과 여덟째 날은 더 이상 따뜻해지는 날이 없으므로 0일이 된다.
이를 구하기 위해서 아래와 같은 순서대로 풀이할 수 있다.
- enumerate를 이용하여 특정 날짜의 인덱스와 온도를 기억한다.
- 온도리스트의 인덱스를 스택에 쌓아두면서
- 만일 현재 온도에 쌓아둔 마지막 날의 온도보다 높다면
- stack을 pop 한다
- 정답에 현재 인덱스와 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
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[프로그래머스]- 기능개발 (0) | 2023.11.16 |
---|---|
[LeetCode] - 유효한 괄호 (0) | 2023.11.15 |
[LeetCode] - 자신을 제외한 배열의 곱 (1) | 2023.11.15 |
[LeetCode] - 주식을 사고팔기 가장 좋은 시점 (0) | 2023.11.14 |
[LeetCode] - 배열 파티션 I (0) | 2023.11.14 |