[Leet code] Daily Temperatures

문제 링크

https://leetcode.com/problems/daily-temperatures/

문제 이해

• 일자 별로 온도가 주어진다.
  ex) [73,74,75,71,69,72,76,73]
• 예를 들어 1일차에는 73도, 2일차에는 74도가 된다.
• 이때, 각 일자별로 더 따뜻해지는 날까지 며칠이 걸리는 지를 나타내는 배열로 반환하면 된다.
  ex) [1,1,4,2,1,1,0,0]
  1일차에는 더 따뜻해지기까지 1일 걸리며, 3일차인 75도에서는 더 따뜻해지는 날까지 4일이 걸리게 된다.

접근 방법

• 온도 배열을 순서대로 순회하며, 더 따뜻해지는 날까지를 얼마나 걸리는 지를 계산하는 방식으로 풀면 되지 않을까?
• 하지만 제한조건을 살펴보면, 온도 배열의 길이 최대값은 100,000이다. 위 방법대로 풀면 시간복잡도 O(N^2)를 소요하게 되어 연산 횟수가 최악의 경우 10,000,000,000번이 되어 시간초과가 발생하게 된다.
• 즉, O(N) 이내에서 해결을 해야하는 상황이며, 온도 배열을 한 번만 순회하면서 문제를 해결해야 한다.
• 순회하며 온도를 그때 그때 관찰하며 이전의 온도와 비교하여 더 높은지를 검사해야한다. 만약 온도가 더 높으면, 이전의 온도와 며칠이 차이나는지, 또 그보다 이전의 온도와 비교하여 더 온도가 높으면, 며칠이 차이나는지를 계산해서 정답에 반영하면 될 것이다.
• 즉, 들어오는 요소가 더 따뜻했을 때 위 동작을 수행하고, 그 다음 요소부터 이어서 관찰하면 되므로, 자료구조 Stack을 사용하는 것이 적절할 것이다. Last in first out이라는 특징을 가진 자료구조이기 때문에, 위 상황을 해결하기에 적합하다.

코드 설계

• 주어지는 temparatures는 온도만 나타낸다. 일자 계산을 편리하게 하기 위해 각 요소를 온도 및 일자로 재구성한다.
• 온도배열과 동일한 길이의 배열을 선언하고, 모든 요소를 0으로 채운다.
  - 각 일자에서 아예 차이가 없을 수 있기 때문에, 우선 0으로 채운다.
• 온도 배열을 순회하며, 스택에 차례대로 담는다. 이때 순회되는 요소가 스택의 가장 위에 담긴 요소보다 크면(온도가 더 따뜻하면) 이전의 날(스택 최상단 요소), 그리고 그 이전의 날들보다 비교하여 요소가 크면 며칠이 차이나는지를 계산하여 정답 배열에 반영한다.
• 그리고 위 조건을 충족했을 때, 스택 최상단 요소는 pop한다.
• 그리고 방금 순회한 요소는 스택에 push한다.
• 위 동작을 모든 온도 배열을 순회할 때까지 반복한다.

코드 구현

const dailyTemperatures = function(temperatures) {
    const temp = temperatures.map((tmp, idx) => ({ tmp, day: idx }));
    const stack = []
    const answer = Array.from({length: temp.length}, () => 0);
    for(let i = 0; i < temp.length; i++) {
        while(stack.length > 0 && stack[stack.length - 1].tmp < temp[i].tmp) {
            const prevDay = stack.pop()
            const currentDay = temp[i].day
            answer[prevDay.day] += currentDay - prevDay.day
        }
        stack.push(temp[i])
    }
    return answer
};