LeetCode - Daily Temperatures 문제 보러가기

문제

문제 해결

쉽게 얘기하면 temperatures에 담긴 값들을 순서대로 비교할 때 현재 인덱스에서 다음 인덱스까지 확인 할 때 자신의 값보다 큰 값을 찾을 때까지의 단계를 계산해서 Output으로 내보내는 것이다.

[73, 74, 75, 71, 69, 72, 76, 73]을 비교하면 73 다음에 큰 값은 74로 한 단계만 넘기면 된다. 그러면 output에는 1이 담긴다.
그 다음 74 다음에 큰 값은 75로, 역시 한 단계만 넘기면 된다. 그러면 다시 1이 추가된다. 현재 output은 [1,1]이다.
그 다음 75는 어떠할까? 75 다음으로 큰 수는 76으로 4단계 정도 가야한다. 그러면 4가 output에 추가된다. [1,1.4]가 된다.
이러한 방식으로 output을 찾는 것이다.
나는 처음에는 일단 시간복잡도를 고려하지 않고, N^2의 시간 복잡도로 해결을 했다.

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        result = []
        for i in range(len(temperatures)) :
            cnt = 0
            chk = 0
            for j in range(i+1, len(temperatures)) :
                if temperatures[i] < temperatures[j] :
                    cnt += 1
                    result.append(cnt)
                    chk = 1
                    break
                else :
                    cnt += 1
            if chk == 0 :
                result.append(0)

        return result

당연히 시간 초과가 떴고 다른 방법을 찾아야했다.
내가 이전에 이행했던 방식은 두 바퀴(?)를 돌리는 것이지만, 해결할 때는 한바퀴를 돌리면서 해결을 해야했다.

일단 answer이라는 리스트에 0들로 미리 선언을 해놓고, stack을 활용해서 문제를 해결한 방법이 있었다.
stack에다가 idx 값들을 넣어두면서 활용을 했고, enumerate 함수를 사용하였다.
(나도 enumerate를 적극 자주 사용해야 한다.)

temperatures를 한 바퀴 돌면서, 인덱스와 값을 가져오고 stack에다가 인덱스를 담으면서 stack 끝에 있는 값이 temperatures 현재의 값 보다 작으면 ansnwer를 업데이트 하는 방식이다.

아까 예시를 들었던 [73,74,75,71,69,72,76,73]를 예로 들면,
처음에 idx와 값은 0과 73이다.
현재는 stack에 아무 값도 들어있지 않기에 바로 넘어가고 stack에 0을 담는다.

다음 단계는 1과 74이다.
현재 stack[-1]의 값은 0이고 temperatures[0]의 값은 73이므로 answer[0]의 값은 1-0으로 1이 된다. 그리고 stack에 1을 담아 stack = [1]이다.

이러한 방식으로 쭉 이어나간다.

전체 코드

class Solution:
    def dailyTemperatures(self, temperatures):
        stack = []
        answer = [0] * len(temperatures)
        for i, next_t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < next_t:
                idx = stack.pop()
                answer[idx] = i - idx
            stack.append(i)
        return answer