.leetcode(739. Daily Temperatures)

문제

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

문제 풀기 전

1. 현재 시점에 영향주는 데이터는 지금의 데이터와 비교해서 높은 숫자가 나올때만
2. 한번에 여러개에 영향을 주는걸 어떻게 풀것인가.

직접 푼 풀이

소요시간: 6분(18:07 ~ 18:13)

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];

        for(int i=0; i<T.length; i++) {
            result[i]= 0;
            for (int j=i+1; j<T.length; j++) {
                if (T[i] < T[j]) {
                    result[i]=j-i;
                    break;
                }
            }
        }

        return result;
    }
}

느낀점

1. 한번에 여러개에 영향을 주는 방식은 없다.(있지만 속도측면에서 일반적으로 쉽게 생각하는 방법과 다르지 않다.)
2. 문제 속에서 종료조건이 있다면 유심히 로직에 이용해볼 생각을 하는게 좋다. 이번에도 마지막이고 미래날짜가 없으면 0으로 한다. 이 조건이 문제 속에 있는데 이 조건을 기반으로 로직을 술술 풀어나가는게 힌트였다.

솔루션 공부 후 추가로 푼 풀이

#종료조건을 이용해서 하나씩 풀어나가는 풀이
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        LinkedList<Integer> stack = new LinkedList<>();

        for(int i=T.length-1; i>=0; i--) {
            while(!stack.isEmpty() && T[i] >= T[stack.peek()]) stack.pop();
            result[i]=stack.isEmpty() ? 0 : stack.peek()-i;
            stack.push(i);
        }

        return result;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)

나중에다시한번

• 최소한의 시간복잡도로 풀어볼 것.