[LeetCode] 739. Daily Temperatures

[목차]

1. 문제 설명
2. 풀이 설명
3. 문제 풀이 source
  3.1 python
  3.2 java

 

1. 문제 설명

 

문제를 조금 설명하자면 날씨 온도의 정보가 들어온다. temperatures 배열이고 저 온도배열에서 첫번째부터 날짜이다. 즉 첫번째 날에는 73도라고 이해하면 된다. 기준이 되는 날짜부터 온도가 올라가는 날이 며칠인지 구하는 문제이다. 

예를 들면 [30,40,20,50] 이라는 배열이 있으면 첫째날 30도의 기준으로 보면 다음날이 40도라서 1일만 기다리면 온도상승이 된다. 따라서 output=[1,0,0,0]이 기록될 것이다. 

두번째 40도인 둘쨋날을 기준으로 보면 다음날 온도가 20도라서 낮아서 무시하고 그 다음날인 넷째날 50도라서 40도보다 높기 때문에 
둘째날부터 넷째날에 온도상승이 있기 때문에 2일을 기록한다. 
즉 output에는 [1,2,0,0]이 기록된다. 

세번째 날인 20도 입장에서는 마찬가지로 다음날이 50도라서 1일만 기다리면 되기 때문에 output= [1,2,1,0]이 나오면 된다. 

그리고 마지막날은 그 다음날이 없기 때문에 0일이라고 보면 된다.즉 마지막에 

output = [1,2,1,0] 이 나와야한다.

 

2. 풀이 설명

문제 풀이 
1. 오늘 온도를 기준으로 해서
  1.1 stack이 비어있으면 현재 날짜 index를 stack에 push
  1.2 stack에 데이터가 있고 내일 온도가 오늘 온도보다 높으면 output배열에서 stack에 있는 index를 꺼낸다. 내일 날짜 - 꺼낸      
        index 를 해서 날짜를 구한다. 그리고 output배열에 해당 index 데이터를 갱신한다.

 

3. 문제 풀이 source

  3.1 python

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    answer = [0] * len(temperatures)
    stack = []
    for cur_day, cur_temp in enumerate(temperatures):
        while stack and stack[-1][1] < cur_temp:
            prev_day, prev_temp = stack.pop()
            answer[prev_day] = cur_day - prev_day

        stack.append((cur_day, cur_temp))

    return answer

  3.2 java

public int[] dailyTemperatures(int[] temperatures) {
        int[] result = 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 pastDay = stack.pop();
                result[pastDay] = i - pastDay;
            }
            stack.push(i);
        }
        return result;
    }