[LeetCode] 739. Daily Temperatures

1. 문제 이해

문제 해석

Daily 온도를 나타내는 an array of integers temperatures 가 입력되면, 마찬가지로 an array of integers answer 를 반환하는데, answer[i] 는 temperatures[i] 가 이후 요소 중 더 높은 수(온도)가 되는 지점과의 offset(the number of days you have to wait)이다.

만약 temperatures[i] 이후 데이터가 없거나, 큰 수가 없을 경우에는 해당 answer[i] 는 0이 된다.

제약 조건 해석

1 ≤ temperatures.length ≤ 10^5,

30 ≤ temperatures[i] ≤ 100

• 시간복잡도를 측정할 실질적인 입력값 n은 temperatures.length 이고, O(n^2) 이상의 복잡도를 갖는 알고리즘은 사용할 수 없다.

2. 접근 방법

먼저 직관적으로 생각하기

• 당장은 이중 반복문을 사용한 방법이 떠올랐지만, 문제 해결에 필요한 자료구조 Stack을 활용하지 못할뿐더러, O(n^2) 이상의 복잡도를 갖는 알고리즘은 사용하면 안된다.
• 정렬을 사용하면 복잡도는 O(nlogn)이 되지만, offset을 구하기 위해서는 각 요소의 원래 index 정보가 필요하기 때문에 순서가 뒤바뀌면 Hash table을 사용해야 할 것 같다.
• Stack 자료구조의 이론만 학습한 채, 아직 개념을 자유자재로 적용할 수 있는 수준이 아닌 것 같다.

활용한 자료구조 & 알고리즘

• Stack

3. 코드 설계 / 구현

레퍼런스 코드

def dailyTemperatures(temperatures):
		# 1. List answer를 선언하고 초기값으로 0을 할당한다.
		# 이렇게 하면 이후 더 높은 수가 나오지 않는 경우나, 마지막 요소일 경우 0을 추가로 할당하지 않아도 된다.
		answer = [0] * len(temperatures)
		# 2. 다음 온도가 현재 온도보다 높지 않을 경우 저장해두기 위한 stack을 만들어 놓는다.
		stack = []
    # 3. enumerate 함수를 활용하여 idx와 value를 동시에 순회하면서
		for cur_day, cur_temp in enumerate(temperatures):

				# 4. stack에 저장된 온도 정보가 있고, stack의 top의 온도가 현재 온도보다 낮다면  
				while stack and stack[-1][1] < cur_temp:
						# 5. stack의 top을 pop, 저장된 idx를 추출하고
						saved_day, _ = stack.pop()
						# 6. answer의 해당 idx에 현재 순회중인 idx와의 offset으로 대체한다.
						answer[saved_day] = cur_day - saved_day

				# 7, 현재 순회중인 데이터의 idx와 온도를 스택에 넣는다.
				stack.append((cur_day, cur_temp))
		return answer

• 위의 코드를 직관적으로 떠올리기는 쉽지 않을 것 같다.
• for loop 안에 while loop가 있어 시간복잡도가 O(n^2)이 되는 것이 아닌가 했지만, 실제 while loop로 탐색하는 것은 stack 안의 data이다.
  • temperatures.length 와 stack에 저장될 data의 수는 연관성이 없다.
    • ex. temperatures[i] 값이 점점 증가만 하는 형태라면 Stack에는 아무것도 담기지 않을 것이고, 점점 감소만 하는 형태라면 Stack에 모두 담길 것이다.
  • 또한 Stack에 데이터가 있고 top < 현재 순회중인 값 일 때만 loop를 돌고, 실질적인 작업pop()과 append() 둘 다 복잡도가 O(1)이다.