★Daily Temperatures★

Daily Temperatures - LeetCode

★다시풀어봐야할 문제★ (접근방법 생각 안나서 강의영상 봄)

접근 방법 [필수 작성]

제한 조건 확인

n이 최대 10^5 이라서 O(n^2) 아이디어로 풀면 안된다.

최소 O(NlogN) 알고리즘을 사용해야한다.

정렬? 후 O(N) ?

→ 20분 정도 고민해봤는데 생각 안나서 강의 영상 봄

아이디어

(idx,temper) 형태의 리스트의 원소를 순서대로 받아서

top 보다 더 큰 temper 가 들어올 경우 더 큰 temper 보다 낮은 temper 를 가지는 index 들에 해당하는answer 값들을 전부 업데이트 해준다.

시간복잡도

O(n)

( 길이가 N 인 리스트를 총 2번 순회한다 )

자료구조

코드 구현 [필수 작성]

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        N = len(temperatures)
        idx_temp = list(enumerate(temperatures))
        # ex: [(0, 73), (1, 74), (2, 75), (3, 71), ... ]
        stack = [idx_temp[0]]
        answer = [0]*N

        for curr_idx in range(1,N):
            while stack and idx_temp[curr_idx][1] > stack[-1][1]:
                past_idx, temp = stack.pop()
                answer[past_idx] = curr_idx - past_idx
            stack.append(idx_temp[curr_idx])
        
        return answer

배우게 된 점 [ 필수 X ]

index 와 관련된 문제를 풀때는 enumerate 활용에 무언가 힌트가 있을 수 있으니, index operation 에 대한 이해를 키워보자.

질문 [ 필수 X ]

자유 형식

피드백 [ 코치 작성 ]

수고하셨습니다!