https://leetcode.com/problems/daily-temperatures/description/
Daily Temperatures - LeetCode
Daily Temperatures - Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for w
leetcode.com
class Solution:
def dailyTemperatures(self, temperatures):
stack = []
result = [0] * len(temperatures)
for i in range(len(temperatures)):
tmp = temperatures[i]
while stack:
if tmp > stack[-1][0]:
result[stack[-1][1] - 1] = i + 1 - stack[-1][1]
stack.pop()
elif tmp <= stack[-1][0]:
break
stack.append((temperatures[i], i + 1))
return result
- 처음에는 stack 자료구조를 도입해 풀 생각을 못했었고, O(n * n)의 시간복잡도를 가진 풀이를 생각해냈다.
- 하지만 조건에 걸리므로
- stack 자료구조에 튜플로 온도를 넣어주고, 특정 조건이 계속 변화하면서 한정적으로 stack 안의 원소에 영향을 끼치는 방법을 이용하여 풀이하였다.
'자료구조 & 알고리즘 관련 > 코딩테스트' 카테고리의 다른 글
| 이진 트리 순회 구현 (0) | 2023.02.03 |
|---|---|
| Longest Consecutive Sequence (0) | 2023.02.01 |
| 수열 정렬 (0) | 2023.01.29 |
| 유기농 배추 (0) | 2023.01.29 |
| 통계학 (0) | 2023.01.28 |
https://leetcode.com/problems/daily-temperatures/description/
Daily Temperatures - LeetCode
Daily Temperatures - Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for w
leetcode.com
class Solution:
def dailyTemperatures(self, temperatures):
stack = []
result = [0] * len(temperatures)
for i in range(len(temperatures)):
tmp = temperatures[i]
while stack:
if tmp > stack[-1][0]:
result[stack[-1][1] - 1] = i + 1 - stack[-1][1]
stack.pop()
elif tmp <= stack[-1][0]:
break
stack.append((temperatures[i], i + 1))
return result
- 처음에는 stack 자료구조를 도입해 풀 생각을 못했었고, O(n * n)의 시간복잡도를 가진 풀이를 생각해냈다.
- 하지만 조건에 걸리므로
- stack 자료구조에 튜플로 온도를 넣어주고, 특정 조건이 계속 변화하면서 한정적으로 stack 안의 원소에 영향을 끼치는 방법을 이용하여 풀이하였다.
'자료구조 & 알고리즘 관련 > 코딩테스트' 카테고리의 다른 글
| 이진 트리 순회 구현 (0) | 2023.02.03 |
|---|---|
| Longest Consecutive Sequence (0) | 2023.02.01 |
| 수열 정렬 (0) | 2023.01.29 |
| 유기농 배추 (0) | 2023.01.29 |
| 통계학 (0) | 2023.01.28 |
