[파이썬 알고리즘 인터뷰] 일일 온도

github.com/onlybooks/algorithm-interview

(22) 일일 온도 

★★Normal

 

[LeetCode]

 

Daily Temperatures - LeetCode

---

풀이법

 1. 당연히 시간초과가 났다. 난이도도 중이였으니 이렇게 풀릴리가 없었다. 

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        for idx,t in enumerate(T):
            cnt = 0
            for other_t in T[idx+1:]:
                cnt+=1
                if other_t > t:
                    T[idx] = cnt
                    break
            else:
                T[idx] = 0
        return T      

 

2. 인덱스를 이용하는 방법이다.

더 큰 값이 나오면 stack을 통해 역주행을 시작한다. 자기보다 큰 값이 나오기전까지 

 

python

 

onlybooks/algorithm-interview

 

java

import java.util.Stack;
 
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int[] answer = new int[T.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && (T[stack.peek()] < T[i])) {
                int last = stack.pop();
                answer[last] = i - last;
            }
            stack.add(i);
        }
        return answer;
    }
}

 

 

아래 문제와 유사하다. 

 

[파이썬 알고리즘 인터뷰] 빗물 트래핑