DFS(깊이 우선 탐색) - Stack 예제 2

1. 문제 이해하기

temperatures 배열은 온도를 나타낸다

73도 에서 더 따뜻해 지는 날은 바로 다음날 74도로 1을 반환한다

다음날 74도에서 따뜻해 지는 날은 75도 하루면 된다 1 반환

다음 75도에서 더 따뜻해지는 날은 76도로 4일을 기다려야한다

.

.

.

마지막 이틀은 따듯해지는 날이 없기 때문에 0을 반환한다

제약조건

첫번째 제약조건은 temperatures의 원소가 많으면 많을 수록 시간 복잡도에 영향을 준다

즉 이 조건은 O(n^2)으로 풀지 말란 뜻임(10^8 을 넘어가면 안되기 때문에)

두번째 제약조건은 온도가 30도부터 100도까지임

2. 코드 설계

def daily_temperatures(temperatures):
    # teperatures의 길이만큼 0으로 초기화
    # 저장할 리스트의 길이를 알고있기 때문에 미리 0으로 초기화 해두면 인덱스를 이용해 값을 편하게 수정할 수 있다.
    # [0, 0, 0, 0, 0]
    ans = [0] * len(temperatures)
    
    # 스택 생성
    stack = []
    
    # 인덱스와 값을 동시에 얻을 수 있게 enumerate(열거형) 사용
    for day, temp in enumerate(temperatures):
        
        # stack이 비어있다면 day, temp가 들어감(stack.append((day, temp))) + 
        # stack의 가장 최근 요소의 1번 인덱스(여기선 온도를 뜻함)가
        # 비교할 온도(위에서 반복문 돌고 있는 요소)보다 작다면 계속 반복
        while stack and stack[-1][1] < temp:
            
            # 만약 비교할 온도보다 stack[-1][1]의 온도가 더 작다면(기존 온도보다 내일 온도가 더 높다면)
            # 기존 스택에 잇는 요소 빼주고 해당 day를 prev_day애 넣어준다
            prev_day = stack.pop()[0]
            
            # ans의 해당 날짜 인덱스에 몇일 기다렸는지 확인해준다
            # 현재 비교중인 날짜에서 전 날짜를 빼면 됨
            ans[prev_day] = day - prev_day
        stack.append((day, temp))
    return ans