739. Daily Temperatures

문제 링크: https://leetcode.com/problems/daily-temperatures/

LeetCode - The World's Leading Online Programming Learning Platform

 

코테 풀면서 종종 나오는 거꾸로 순회해서 푸는 문제. 개인적으로는 네이버 인턴 코테나 카카오 코테에서 봤던 기억이 난다. 뭔가 문제를 풀다가 O(N) 비스무리하게 풀어야 하는데 정방향으로 순회했을 때 N^2 풀이밖에 떠오르지 않는다면 역방향 순회로 풀어본다.

 

역방향으로 순회한다는 아이디어를 떠올린다면 쉽게 풀리는 문제. 가장 가까운, 큰 숫자를 찾으면 되기 때문에, 역방향으로 순회하면서 그리디하게 현재 위치에서 찾아야 하는 곳의 온도를 찾으면 된다. 매 번마다 O(N)으로 찾을 필요가 없다는 점에 주의하면 될 것 같다.

 

	class Solution:
	def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
	n = len(temperatures)
	sol = [0]*n
	stack = []
	for idx in range(len(temperatures)-1, -1, -1):
	cur = temperatures[idx]
	while stack and cur >= temperatures[stack[-1]]:
	stack.pop()
	if stack:
	sol[idx] = stack[-1]-idx
	stack.append(idx)
	return sol

view raw Daily Temperatures.py hosted with ❤ by GitHub