인프런 커뮤니티 질문&답변

안녕하세요 강사님, Daily temperatures 문제 시간 복잡도에 의문이 생겨서 질문 드립니다.

강의에서 말씀해주신 코드가 아래와 같은데요

def daily_temperatures(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
        stack.append((day, temp))
    return ans

첫번째 for 부분에서 시간 복잡도가 O(n)이고,

두번째 while문이 왜 시간복잡도가 O(1)인지 좀 헷갈립니다.

list의 pop의 시간복잡도가 O(1)이긴 한데, 이것도 n번 반복하면 O(n)이지 않나요?

while문에서 최대한 pop이 일어날수 있는 수가 n번 ? 같아서 질문 드립니다.

감사합니다.