739. Daily Temperatures

주어진 배열의 값이 화씨이고, 몇번째 뒤에 나보다 큰 온도가 나오는지 확인하는 문제 

 

[73, 74, 75, 71, 69, 72, 76, 73]

만약 [0]번째인 73은 바로 1일 뒤에 74가 온다. 따라서 1일 뒤에 더 따뜻한 날씨가 나온다. 

[1, 1, 4, 2, 1, 1, 0, 0]

 

1) 이중 for문으로 풀어봤지만, 시간 초과 

    def dailyTemperatures(self, T: [int]) -> [int]:
        # 기본값이 0인 배열을 만드는 방법 2가지
        # ans = [0] * len(T)
        # ans = [0 for _ in range(len(T))]
        ans = [0] * len(T)

        for i in range(len(T)):
            cnt = 1
            for j in range(i+1, len(T)):
                if T[i] < T[j]:
                    ans[i] = cnt
                    break
                cnt += 1
        return ans

O(n)번만에 풀 수 있는 방법이 있을까? --> stack 활용

 

2) stack 활용

현재 값과 stack의 top값을 비교해서, 현재값이 더 크면 stack의 top이 종료...

[73, 74, 75, 71, 69, 72, 76, 73]이 있으면 

stack = 73

현재 값이 74이면,  stack top < 현재값 이므로, 73의 정답은 1이 된다. 

stack top보다 작은 값이면 계속해서 stack에 쌓는다. 

stack top보다 큰 값이면, POP하고 해당 index 지점에 값을 넣는다. 

 

이 경우에는 stack에 값을 저장하는 것이 아니라, 위치(index)를 저장하면서 문제를 해결해야된다. 

    def dailyTemperatures(self, T: [int]) -> [int]:
        # 기본값이 0인 배열을 만드는 방법 2가지
        # ans = [0] * len(T)
        # ans = [0 for _ in range(len(T))]
        ans = [0] * len(T)
        stack = []
        for i, value in enumerate(T):
            while stack and T[stack[-1]] < value:
                pos = stack.pop()
                ans[pos] = i - pos
            stack.append(i)
        return ans

index를 어떻게 활용해야되는지 배운 문제