[Leetcode] Daily Temperatures
- 1 5
- 30
1
2
3
4
5
6
7
8
9
10
def dailyTemperatures_timelimited(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
output = [0 for _ in range(n)]
for i in range(n):
temp = temperatures[i]
for j in range(i + 1, n): # i+1부터 시작
if temperatures[j] > temp:
output[i] = j - i # 인덱스 차이가 일수
break
return output
더 나은 방식으로 스택
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
result = [0] * n
stack = [] # (index, temperature) 저장
for i in range(n):
# 현재 온도가 스택의 온도들보다 높으면 처리
while stack and temperatures[i] > stack[-1][1]:
prev_idx, prev_temp = stack.pop()
result[prev_idx] = i - prev_idx
stack.append((i, temperatures[i]))
return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
**핵심 아이디어:**
1. **스택**에 아직 답을 찾지 못한 인덱스들을 저장
2. 현재 온도가 스택 top의 온도보다 높으면 → 그 날들의 답을 찾은 것
3. 스택에서 pop하면서 결과 배열에 일수 차이 저장
**동작 과정 예시:**
`temperatures = [73,74,75,71,69,72,76,73]`
```
i=0: stack=[(0,73)]
i=1: 74>73, result[0]=1, stack=[(1,74)]
i=2: 75>74, result[1]=1, stack=[(2,75)]
i=3: 7169, result[4]=1, 72>71, result[3]=2, stack=[(2,75),(5,72)]
i=6: 76>72, result[5]=1, 76>75, result[2]=4, stack=[(6,76)]
i=7: 73<76, stack=[(6,76),(7,73)]
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.