Daily Temperatures

🔗 문제 링크

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

🔍 문제 설명

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

⚠️ 제한사항

• $1 <= temperatures.length <= 10^5$

• $30 <= temperatures[i] <= 100$

🗝 풀이 (언어 : Java)

스택을 이용하여 해당 순서의 값보다 작은 것들을 스택에서 계속 지워주면서 반복문을 한번만 돌면서 해결하는 알고리즘이다. 스택에 들어갈 때 해당 값의 인덱스를 보관해주고(반복문의 인덱스 - 해당 값 인덱스 = 정답 인덱스 값) 값은 배열[스택 인덱스 값] 형태로 참조한다. 원래 스택에 남은 값들은 다 0으로 처리해주어야 하는데 정답 배열 선언시 초기화 값이 0이라 별도의 처리가 필요없다.

import java.util.Stack;

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                int idx = stack.pop();
                answer[idx] = i - idx;
            }
            stack.push(i);
        }
        return answer;
    }
}