9장 스택,큐(3) - 스택이란? (예제-일일 온도)

 

 

매일의 화씨 온도 리스트 T를 입력 받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라.
입력: T = [73, 74, 75, 71, 69, 72, 76, 73]
출력: [1,1,4,2,1,1,0,0]

 

def dailyTemperatures(T: list[int]) -> list[int]:
    answer = [0] * len(T)  # 결과를 저장할 리스트, 초기값은 0
    stack = []  # 인덱스를 저장하는 스택
    
    for i, cur in enumerate(T):  # 인덱스(i)와 현재 온도(cur)를 함께 순회
        # 스택이 비어 있지 않고, 현재 온도가 스택의 마지막 인덱스에 해당하는 온도보다 높다면
        while stack and cur > T[stack[-1]]:
            last = stack.pop()  # 스택에서 인덱스를 꺼냄
            answer[last] = i - last  # 현재 인덱스와의 차이를 계산하여 결과에 저장
        stack.append(i)  # 현재 인덱스를 스택에 추가
        
    return answer

 

 

코드 동작 과정

1. answer 리스트 초기화:
   • answer 리스트는 입력 리스트 T와 같은 길이로 생성되며, 모든 값을 0으로 초기화한다.
   • answer[i]는 T[i] 이후 더 따뜻한 날까지 기다려야 하는 날의 수를 저장한다.
2. 스택의 역할:
   • 스택은 아직 더 따뜻한 날을 찾지 못한 날의 인덱스를 저장한다.
   • 스택의 LIFO(Last In, First Out) 구조를 이용하여, 현재 온도가 더 높은 날을 만나면 스택에서 값을 제거하며 결과를 계산한다.
3. while 조건:
   • 스택이 비어있지 않고, 현재 온도(cur)가 스택의 마지막 인덱스에 해당하는 온도(T[stack[-1]])보다 높다면:
     • 스택에서 인덱스를 꺼내고(stack.pop()), 현재 인덱스와의 차이를 계산하여 answer에 저장한다.
   • 이 과정이 끝나면 현재 인덱스를 스택에 추가한다.
4. 결과 반환:
   • 루프가 끝난 후, answer 리스트를 반환한다.
   • 스택에 남아 있는 인덱스들은 더 따뜻한 날이 없는 날짜로, 해당 값은 이미 0으로 초기화되어 있다.

---

예제와 상세 실행 과정

• 입력: T = [73, 74, 75, 71, 69, 72, 76, 73]
• 예상 출력: [1, 1, 4, 2, 1, 1, 0, 0]

단계별 실행:

 

1. 초기화:

• answer = [0, 0, 0, 0, 0, 0, 0, 0]
• stack = []

 

2. 첫 번째 날 (i = 0, cur = 73):

• stack은 비어 있으므로, stack.append(0) 실행.
• stack = [0]

 

3. 두 번째 날 (i = 1, cur = 74):

• 현재 온도(74) > 스택의 마지막 인덱스에 해당하는 온도(73):
  • last = stack.pop() → last = 0, stack = []
  • answer[0] = 1 - 0 = 1
• stack.append(1) 실행.
• answer = [1, 0, 0, 0, 0, 0, 0, 0], stack = [1]

 

4. 세 번째 날 (i = 2, cur = 75):

• 현재 온도(75) > 스택의 마지막 인덱스에 해당하는 온도(74):
  • last = stack.pop() → last = 1, stack = []
  • answer[1] = 2 - 1 = 1
• stack.append(2) 실행.
• answer = [1, 1, 0, 0, 0, 0, 0, 0], stack = [2]

 

5. 네 번째 날 (i = 3, cur = 71):

• 현재 온도(71) ≤ 스택의 마지막 인덱스에 해당하는 온도(75), 스택에 추가:
  • stack.append(3)
• stack = [2, 3]

 

6. 다섯 번째 날 (i = 4, cur = 69):

• 현재 온도(69) ≤ 스택의 마지막 인덱스에 해당하는 온도(71), 스택에 추가:
  • stack.append(4)
• stack = [2, 3, 4]

 

7. 여섯 번째 날 (i = 5, cur = 72):

• 현재 온도(72) > 스택의 마지막 인덱스에 해당하는 온도(69):
  • last = stack.pop() → last = 4, stack = [2, 3]
  • answer[4] = 5 - 4 = 1
• 현재 온도(72) > 스택의 마지막 인덱스에 해당하는 온도(71):
  • last = stack.pop() → last = 3, stack = [2]
  • answer[3] = 5 - 3 = 2
• stack.append(5)
• answer = [1, 1, 0, 2, 1, 0, 0, 0], stack = [2, 5]

 

8. 일곱 번째 날 (i = 6, cur = 76):

• 현재 온도(76) > 스택의 마지막 인덱스에 해당하는 온도(72):
  • last = stack.pop() → last = 5, stack = [2]
  • answer[5] = 6 - 5 = 1
• 현재 온도(76) > 스택의 마지막 인덱스에 해당하는 온도(75):
  • last = stack.pop() → last = 2, stack = []
  • answer[2] = 6 - 2 = 4
• stack.append(6)
• answer = [1, 1, 4, 2, 1, 1, 0, 0], stack = [6]

 

9. 여덟 번째 날 (i = 7, cur = 73):

• 현재 온도(73) ≤ 스택의 마지막 인덱스에 해당하는 온도(76), 스택에 추가:
  • stack.append(7)
• stack = [6, 7]

 

10. 최종 결과:

• answer = [1, 1, 4, 2, 1, 1, 0, 0]

---

시간 및 공간 복잡도

1. 시간 복잡도:
   • 각 인덱스는 최대 한 번 스택에 추가되고, 한 번 제거되므로 O(n)
2. 공간 복잡도:
   • 스택의 최대 크기는 입력 리스트의 길이에 비례하므로 O(n)