[LeetCode] 739. daily_temperatures (Medium) 2023/5/9

문제 제목	정답률	난이도
739. daily_temperatures	66.3%	Medium

Daily Temperatures - LeetCode

 

문제요약

문자형을 원소로 가지는 배열이 주어질 때, 오늘보다 더 따뜻한 날씨를 위해서는 얼마의 날들을 더 기다려야 하는지에 대한 배열을 반환해라

조건 1) 문자열의 길이는 1 이상이고, 원소는 30 이상 100 이하의 정수 값이 주어진다

 

 

풀이 1

스택이용 (단, 스택에 값을 저장하지 않고 인덱스를 저장한다)

Step1. 상승구간 판단(이전 값보다 값이 큰 지점을 확인)

• 상승구간이 아니면 스택에 해당 온도값과 대응되는 인덱스 저장
• 상승구간이면 스택의 값들과 비교하여 현재 값이 더 큰 지점들에 대해 결과 리스트에 날짜 계산하여 업데이트 후, 해당 지점을 스택에서 삭제

 

 

구현 (1132ms)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        idx_stack=[]
        result=[0 for i in range(len(temperatures))]
        for idx, value in enumerate(temperatures):
            while len(idx_stack)!=0 and value>temperatures[idx_stack[-1]]:
                last_idx=idx_stack.pop()
                result[last_idx]=(idx-last_idx)
            idx_stack.append(idx)
        return result