22. Daily Temperatures

아현·2021년 3월 28일
0

Algorithm

목록 보기
23/400
post-custom-banner

리트코드

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



설명

  • 화씨 73도인 첫째 날에서 더 따뜻한 날을 위해서는 하루만 기다리면 된다. 바로 다음날인 둘째 날은 화씨 74도다.
    마찬가지로 더 따뜻한 날을 위해서는 셋째 날까지 하루만 기다리면 된다.
    셋째 날은 화씨 75도며, 이 보다 더 따뜻한 날을 위해서는 4일을 더 기다려야 일곱째 날 화씨 76도가 된다.
    일곱째 날과 여덟째 날은 더 이상 따뜻한 날이 없으므로 각각 0이다.



1. 스택 값 비교


class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        
        answer = [0] * len(T)
        stack = []
        for i, cur in enumerate(T):
            #현재 온도가 스택 값보다 높다면 정답철
            
            while stack and cur > T[stack[-1]]:
                last = stack.pop()
                answer[last] = i - last
                
            stack.append(i)
            
        return answer


  • 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서, 더 높다면 스택의 값을 팝으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.



  • 입력값 [73, 74, 75, 71, 69, 72, 76, 73] 일 때 인덱스가 5인 지점(인텍스는 0부터 시작)에서 스택에는 [2, 3, 4]가 있다.

    • 계속 온도가 떨어지면 처리되지 못하고 스택에 계속 쌓이기 때문
  • 2, 3, 4의 온도는 각각 75, 71, 69이다.
    72는 71, 69보다 높기 때문에 현재 인덱스와 71 인덱스와는 두 칸 차이로 정답은 2가 되고, 69의 인덱스와는 한 칸 차이로 정답은 1이다.

  • 처리한 인덱스는 스택에서 팝으로 제거된다.

  • 75도인 2는 현재 온도보다 높기 때문에 계속 스택에 남아 있게 된다.

    • 스택에는 [2, 5]가 남아 있고, 각각 75, 72이다.
  • 이제 현재 온도 76도는 72, 75보다 모두 높기 때문에 스택은 모두 처리되어 비워질 것이다.

  • 72의 인덱스와는 한 칸 차이로 정답은 1이고, 75의 인덱스와는 4칸 차이가 난다.

  • 디폴트는 0이다.

    • 만약 더 높은 온도가 나오지 않아 스택이 비워지지 않았다면 해당 인덱스는 해당 없음, 즉 문제에서 요구하는 바와 같이 0으로 남게 된다.
profile
For the sake of someone who studies computer science
post-custom-banner

0개의 댓글