리트코드739-스택

리트코드-739일일온도
우선 생각나는 방법은 당연하게 브루트 포스였다.
이중 for문으로 i,j로 순서대로 순회하며 T[i]보다 큰 T[j]가 발견되면
answer[i]=j-i 를 할당하는 방식이다. 하지만 시간복잡도가 좋지 않다.

다음으로 생각해본 방식은 투 포인터이다. 그런데 기다려야 하는 일수의 최소값을 구해야 하므로 포인터는 바로 옆의 인덱스부터 시작하는 것이 효율적이다. 하지만 이러면 그냥 이중for문으로 순회하는 것과 별반 차이가 없다. 몇일을 기다릴지(인덱스의 차)를 계산해야하므로 리스트를 정렬하는 조작을 하기도 어려워 투포인터는 적합하지 않은 방식으로 보였다.

스택에 온도가 큰 수가 위로 오게 넣고 pop해나가며 인덱스의 차를 기다려야 하는 일수로 할당하는 방법을 생각해보았다.
하지만 T는 시간순으로 정렬되있기에 온도가 높아도 이전 날짜면 기다릴수 없다.(인덱스의 차가 마이너스이다.)

인덱스를 순회하면서 미래에 순회할 인덱스에 있는 나보다 큰값에 대한 정보를 미리 알 수 있는 방법이 없을까?
그런데 생각해보니 굳이 인덱스 하나하나마다 즉시 기다릴 날짜를 할당할 필요는 없었다. 리스트를 순회하며 더 큰 온도가 나올때까지 기다렸다가 발견되면 그 때 한꺼번에 밀렸던 기다릴 일수를 할당하면 될 것 같다. 이 한꺼번에 처리를 하기위해 스택을 사용하면 될 것 같다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer=[0]*len(temperatures)
        stack=[]
        for i,temp in enumerate(temperatures):
            #쌓여진 것보다 큰 온도가 발견되면 answer할당
            while stack and temp>temperatures[stack[-1]]:
                idx=stack.pop()
                answer[idx]=i-idx
            stack.append(i)
        return answer
                
                    

처음에 enumerate를 사용하지 않고 .index로 접근해보았으나 같은 값이 2개이상 있을경우 리스트는 처음발견된 index를 반환하기에 정확한 index를 반환하지 않는 경우가 있었다. enumerate를 사용하는 습관을 들여야겠다.