알고리즘 - 일일 온도

스택

스택을 이용해 푸는 문제
temperatures에 들어있는 수보다 큰 수가 나올때까지 걸리는 index의 차이를 구한다
예를들어 temperatures[2]는 temperatures[6]이 나올 때까지 큰 수가 나오지 않으므로 output은 4가 된다.

이런 식의 리스트와 리스트의 거리/깊이를 구하는 것은 스택을 이용해서 푸는 것 같다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        temp = temperatures
        stack = []
        answer = [0] * len(temp) #기온 데이터 길이만큼 0을 담아 생성. 
								0은 해당 데이터 뒤에 더 큰 수가 나오지 않으면 0을 반환한다
        for i,last in enumerate(temp):
            while stack and last > temp[stack[-1]] : 
                #마지막보다 큰 수가 들어오면 작거나같은 수가 나올 때 까지
                lastStack = stack.pop() #마지막 스택을 꺼냄. 스택에는 해당 기온의 index위치가 적혀있음
                answer[lastStack] = i - lastStack #거리 계산해서 답에 넣어주기
            stack.append(i) # 비교한 데이터는 스택에 넣기
        return answer

조건1. stack의 마지막 데이터가 temp[i]보다 크면 스택에 쌓는다
조건2. stack의 마지막 데이터가 temp[i]보다 작으면 스택에서 삭제한다
조건3. 스택은 내림차순으로 쌓이고 항상 마지막 데이터는 스택에 쌓인다

위의 조건대로 for과 while을 돌려 i와 스택에 저장되있는 index와의 차이를 구하면 해당 데이터의 거리를 구할 수 있다.

후기

다행히 이해하는데 크게 어렵진 않았던 문제.
알고리즘 문제를 풀때 스택개념을 빠르게 캐치하는 것이 관권일 것 같다.