Daily Temperatures

[hsskey]

Daily Temperatures

매일의 온도를 나타내는 int형 배열 temperatures가 주어진다. answer 배열의 원소 answer[i]는 i번 째 날의 온도보다 더 따뜻해지기까지 며칠을 기다려야하는지 나타낸다. 만약 더 따뜼해지는 날이 없다면 answer[i] === 0이다. answer 배열을 반환하는 함수를 구현하시오

📝 제약조건

• 1 <= temperatures <= 10^5
• 30 <= temperatures[i] <= 100

💡 예시

• Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

  • Output: [1, 1, 1, 0]

• Input: temperatures = [30, 40, 50, 60]

  • Output: [1, 1, 1, 0]

• Input: temperatures = [30, 60, 90]

  • Output: [1, 1, 0]

문제 해결 과정

Step 1: 문제 이해하기

• 제약조건, input, output을 확인하여 문제를 정확히 파악합니다.

Step 2: 접근 방법

• 직관적으로 생각하기

  • 제약조건에 의해 N^2 풀이는 시간초과 ❌
  • 배열의 순서가 중요하므로 nlogn으로 풀 수 있는 sort도 제외 ❌

• 자료구조와 알고리즘 활용

  • 괄호유효성 검사 문제와같이 특정조건에 반응한다 → Stack 사용

Step 3: 코드 설계

answer = []
stack = [] // 스택선언
for t in temperature
    while(stack.top < item)
        stack.pop()
        며칠을 기다렸는지
        answer 업데이트
    stack.push([item, index])

console.log(answer)

Step 4: 코드 구현

• 설계한 알고리즘에 따라 코드를 작성하고 테스트합니다.

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
    const stack = []
    const answer = new Array(temperatures.length).fill(0)

    for(let i = 0; i < temperatures.length; i++) {
        const current_temp = temperatures[i]
        while(stack && stack.at(-1)?.[1] < current_temp) {
            const [prev_day, _] = stack.pop()
            answer[prev_day] = i - prev_day
        }
        stack.push([i, temperatures[i]])

    }

    return answer
};

console.log(dailyTemperatures([5, 4, 3, 7]))