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

조철호님의 프로필 이미지

작성한 질문수

코딩테스트 [ ALL IN ONE ]

Daily temperatures 시간 복잡도 질문

해결된 질문

24.01.07 00:22 작성

·

226

1

안녕하세요 강사님, 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번 ? 같아서 질문 드립니다.

 

감사합니다.

답변 1

0

개발남노씨 강의 관리자님의 프로필 이미지

2024. 01. 08. 16:13

안녕하세요 철호님! 해당 질문의 답변은 영상으로 설명드리는 게 좋을 듯하여 커리큘럼에 추가했습니다!~ 참고해 주세요 :)

image