[LeetCode] Medium. Daily Temperatures

문제 링크: https://leetcode.com/problems/daily-temperatures/

Daily Temperatures - LeetCode

접근

• 해당 문제의 시간복잡도에 들어가는 배열의 길이가 10^5이므로, 시간복잡도 O(n) 밑으로 계산해야 한다.
• 각 날의 온도를 타깃으로 하여 언제 따뜻한 날이 오는지 for문을 돌리게 되면 시간 초과가 발생한다.

코드

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer = [0] * len(temperatures)
        stack = []
        for day,t in enumerate(temperatures):
            while stack and stack[-1][1] < t:
                prev_day,prev_t = stack.pop()
                answer[prev_day] = day - prev_day
            stack.append((day,t))
        return answer

 

풀이

• 스택을 이용하여 해결했다.
• 유효한 괄호식인지 해결하는 문제처럼 해결하면 용이하다
  • 여는 괄호이면 푸시
  • 닫는 괄호이면, 가장 최근에 넣은 값이랑 짝이 맞으면 팝, 다를 경우 False
  • 모든 체크가 끝났을 때, 스택이 비어있으면 True, 스택에 값이 있으면 False
• 더 들어가야 할 만한 점은, 괄호는 짝이 있으나, 이 문제는 현재 t보다 낮은 모든 온도에 대해 pop이 이루어져야 한다는 점이다.
• stack에 인덱스, 값을 튜플로 넣어두고, 값을 뺄 때에는 stack [-1][1]과 t를 비교한다.
• stack에 넣은 값이 t보다 작은 모든 값을 다 팝 해주고, 팝할때마다 튜플의 0번째 값인 인덱스와, 현재 t에 대한 인덱스 day를 뺀 값을 넣어준다.