[코테 적용] LIFO 2번째 문제

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

코테 적용 방법

Stack의 다양한 활용
1. LIFO 특성을 활용한 문제 ⭐
2. DFS(깊이 우선 탐색)에 사용 ⭐

문제 풀이 방법

1. 문제 이해하기
2. 접근 방법
3. 코드 설계
4. 코드 구현

문제

(https://leetcode.com/problems/daily-temperatures/)

접근 방법

한번씩 훑으니 O(n^2)?

Stack을 이용하면 O(n)에 끝낼 수 있다.

코드 설계

스택을 선언하고
반복문을 한번 돌면서 작업

코드 구현

---

시간복잡도 추가 설명

nums = [1, 2, 3, 4, ..., 10000]
n = len(nums)

for i in range(n):
    print("A")

#########################

# 반복문이 있다고 n이 아니라 실행을 생각해보자
# O(n) 

for i in range(n):
    for j in range(10):
        print("A")

######################


# n번 반복하는데, while문의 코드는 실행할때마다 n번이 아니고, 전체 합해서 n번이다
def solution(temperatures):
    ans = [0] * len(temperatures)
    stack = []
    for day, temp in enumerate(temperatures):
        while stack and stack[-1][1] < temp:
            prev_day = stack.pop()[0]
            ans[prev_day] = day - prev_day
            print("A")
        stack.append((day, temp))
    return ans