[leetcode] 739. Daily Temperatures

⏱️ 소요시간

하루 이상.
먼저 생각한 풀이의 시간복잡도는 이중반복문을 이용하여 O(N^2)로, 이것보다 더 줄일 수 있는 방법을 생각하지 못함.

📚 문제 요약

[leetcode] daily temperatures

📑 풀이 요약

온도 리스트를 오른쪽부터 접근하면서, stack에는 더 따뜻한 날의 후보 인덱스가 들어가게 된다.
for문에서 가리키는 현재 온도와 stack의 최상단의 더 따뜻한 후보 날짜 온도 두 개를 비교하여

1. 현재 온도 < stack 최상단에 있는 후보 온도
   => 더 따뜻한 날을 만났기 때문에 (후보 날짜 인덱스 - 현재 온도 인덱스) = (걸린 시간)을 결과 리스트에 저장.
   현재 온도는 앞으로 탐색할 날의 더 따뜻한 날의 후보가 될 수 있으므로 stack에 저장

2. 현재 온도 >= stack 최상단에 있는 후보 온도
   => 앞으로 나오게 될 날보다 더 따뜻한 날은 현재 온도이지 stack 최상단에 있는 후보 온도가 아니다. 따라서 현재온도 < stack 최상단에 있는 후보 온도 조건이 성립할 때까지 stack에서 최상단 노드를 계속해서 pop. 현재 온도는 앞으로 탐색할 날의 더 따뜻한 날의 후보가 될 수 있으므로 stack에 저장

📑 풀이 상세 설명

직접 문제 예제를 통해 동작 과정을 살펴보자. 반복문을 풀어 설명하기에 풀이가 길지만 호흡 한 번 하고 천천히 읽어보면 이해가 될 것이다.

온도 리스트(temp)를 맨 뒤부터 탐색해나간다.
결과 리스트(res)는 온도 리스트와 동일한 사이즈, 값은 0으로 초기화시킨다.

for문으로 온도리스트 맨끝부터 탐색해나며, stack에 더 따뜻한 날 후보를 저장해나가자. (따뜻한 날 후보는 stack에 push해가다가 후보가 될 수 없다 판단하면 stack에서 pop) stack에는 **탐색 날짜 온도를 기준, 오른쪽에 있는 날들 (=더 따뜻해지는 날이 될 수 있는 후보)가 담겨있다.

<반복 1회>
cur : 73 (idx : 7) , stack = []

스택이 비어있다 = 더 따뜻한 날의 후보들이 존재하지 않는다. = 7번째 날 기준 오른쪽에는 더 따뜻한 날이 존재하지 않는다.

7번째 날의 온도는 앞으로 탐색하게 될 날들 (0번째 ~ 6번째) 기준 오른쪽에 위치하면서 처음 만나는 더 따뜻한 날의 후보가 될 수 있으므로 stack에 추가한다. (예시에서는 이해를 위해 온도 값 자체를 추가하지만, 인덱스 번호를 추가하는게 훨씬 편하다)

<반복 2회>
cur : 76 (idx : 6) , stack = [73]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다. = 현재 탐색하는 6번째 날의 온도(76)와 7번째 날의 온도(73)를 비교한다.

6번째날의 온도 (76)가 7번째 날의 온도 (73)보다 높다. 이는 앞으로 탐색하게 될 날들 (0번째~5번째) 기준, 6번째 날이 더 따뜻한 날의 후보가 됨을 말한다. (7번째 날은 후보가 될 수 없다. 6번째 날이 더 크니까)=> stack에 있는 7번째 온도를 pop하고, 6번째 날의 온도를 append한다.

<반복 3회>
cur : 72 (idx : 5) , stack = [76]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 5번째 날의 온도(72)와 스택에 있는 후보 (6번째 날 온도, 76)를 비교한다.

현재 탐색하는 온도 (72)보다 후보의 온도(76)이 더 높다 -> 5번째 날(72) 기준 더 따뜻한 날은 6번째 날(76)에 온다 -> res[5] = 6번째-5번째 = 1 (언제 오는지 day를 res[5]에 업데이트)
(res[5] = 1 #5번째 날일때는 1일 후에 더 따뜻한 날이 온다)

앞으로 탐색하게 될 날 (0번째~4번째)들 기준 더 따뜻한 날의 후보로 5번째도 가능하기에 stack에 5번째 날의 온도(72)를 append한다.

<반복 4회>
cur : 69 (idx : 4) , stack = [76, 72]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 4번째 날의 온도(69)와 스택에 있는 후보를 비교한다. (top에 존재하는 5번째 날의 온도 72)

현재 탐색하는 4번째 날의 온도 (69)보다 후보의 온도(5번째 날, 72)이 더 높다 -> 4번째 날 기준 더 따뜻한 날은 5번째 날에 온다 -> res[4] = 5번째-4번째 = 1 (언제 오는지 day를 res[4]에 업데이트)
(res[4] = 1 #4번째 날일때는 1일 후에 더 따뜻한 날이 온다)

앞으로 탐색하게 될 날 (0번째~3번째) 기준 더 따뜻한 날의 후보로 4번째도 가능하기에 stack에 4번째 날의 온도(69)를 append한다.

<반복 5회>
cur : 71 (idx : 3) , stack = [76,72 69]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 3번째 날의 온도(71)와 스택에 있는 후보를 비교한다. (top에 존재하는 4번째 날의 온도 69)

현재 탐색하는 3번째 날의 온도 (71)가 후보의 온도(4번째 날, 69)보다 높다. 이는 후보 (4번째 날, 69)가 탈락됨을 의미한다. stack에서 pop하고 다음 후보 (5번째 날, 72)를 살펴보자.
pop한 뒤의 stack = [76, 72, 69]

현재 탐색하는 3번째 날의 온도 (71)보다 후보의 온도 (5번째 날, 72)가 더 높다. 따라서 res[3] = 5-3 = 2 로 업데이트가 가능하다는 것이다. 그리고 3번째 날의 온도 71은 앞으로 탐색할 0~2번째 날 기준 더 따뜻한 날의 후보가 될 수 있으므로 stack에 push한다.

<반복 6회>
cur : 75 (idx : 2) , stack = [76,72 71]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 2번째 날의 온도(75)와 스택에 있는 후보를 비교한다. (top에 존재하는 3번째 날의 온도 71)

현재 탐색하는 2번째 날의 온도 (75)가 후보의 온도(3번째 날, 71)보다 높다. 이는 후보 (3번째 날, 71)가 탈락됨을 의미한다. stack에서 pop하고 다음 후보를 살펴보자. (다음 후보 : 72)
pop한 뒤의 stack = [76, 72, 71]

마찬가지로 현재 탐색 온도 (75) > 지금 후보 (72) 이므로 지금 비교하는 후보를 탈락시키고 다음 후보를 살펴보자.
pop한 뒤의 stack = 76, 72]

현재 탐색 온도 (75) < 지금 후보 (76) 이므로 res[2]의 값을 업데이트한다. res[2] = 6-2 = 4

현재 탐색 온도 75는 앞으로 탐색하게 될 날 (0~1번째)의 더 따뜻한 날의 온도가 될 수 있기 때문에 stack에 push한다.

<반복 7회>
cur : 74 (idx : 1) , stack = [76,75]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 1번째 날의 온도(74)와 스택에 있는 후보를 비교한다. (top에 존재하는 2번째 날의 온도 75)

현재 탐색하는 1번째 날의 온도 (74)보다 후보의 온도 (2번째 날, 75)가 더 높으므로 res[1] = 2-1 = 1. 1번째 날의 온도는 앞으로 탐색하게 될 0번째 날의 더 따뜻한 날 후보가 될 수 있으므로 stack에 push한다.

<반복 8회>
cur : 73 (idx : 0) , stack = [76,75, 74]

스택에 값이 있다 = 더 따뜻한 날의 후보가 존재한다 = 현재 탐색하는 0번째 날의 온도(73)와 스택에 있는 후보를 비교한다. (top에 존재하는 1번째 날의 온도 74)

현재 탐색하는 0번째 날의 온도 (73)보다 후보의 온도 (1번째 날, 74)가 더 높으므로 res[0] = 1-0 = 1. 반복 종료.

💻 전체 코드 (제출 코드)

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        n = len(temperatures)
        res = [0 for _ in range(n)]
        for i in range(n-1, -1, -1): #idx
            while stack and temperatures[stack[-1]] <= temperatures[i]:
                idx = stack.pop()
            if stack: #스택이 비지 않았다면
                res[i] = stack[-1]-i
            stack.append(i)
        return res
                

💡 새롭게 알게 된 사실 or 어려웠던 점

조건에 따르면 온도 리스트의 원소 개수는 최대 10^5개이다.
시간복잡도가 O(N)이며 N = 10^8 일 때 (1억) 프로그램이 돌아가는데 걸리는 시간이 약 1초라고 한다. 이 문제에서 이중반복문을 사용하게 된다면 시간복잡도는 O(N^2)으로 N^2 = (10^5)^2 = 10^10 = 100억이므로 10초가 걸리게 된다. 이중반복문을 이용하여 푸는 방법은 잘못 접근했음을 인지하고 다른 방식을 떠올려야 했다.

문제를 볼 때는 스택을 왜 사용해야 하는지 떠올리지 못하였다. 블로그의 여러 풀이를 보더라도 스택을 사용해서 시간복잡도를 줄인 건 알겠지만, 그렇다고 이 문제를 풀 때 스택을 떠올리는 이유가 궁금했다. 아래 블로그를 보고 스택을 사용하는 이유에 대해 이해할 수 있었다.

😻 도움을 받은 사이트

https://reakwon.tistory.com/196
이 문제를 해결했다면 백준의 17298번의 오큰수 문제도 풀어보길 바란다!