Lv.2arraymonotonic-stackstack
더 따뜻한 날까지
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
정수 배열 T가 주어집니다. T[i]는 i일째의 기온입니다.
각 날에 대해, 자기보다 기온이 높은 날이 처음 오기까지 며칠을 기다려야 하는지 담은 배열을 반환하세요. 그런 날이 없으면 0입니다.
입출력 예
| T | result |
|---|---|
[73, 74, 75, 71, 69, 72, 76, 73] | [1, 1, 4, 2, 1, 1, 0, 0] |
[30, 40, 50, 60] | [1, 1, 1, 0] |
[60, 50, 40] | [0, 0, 0] |
입출력 예 설명
예 1 — 0일째(73)는 1일째(74)에 바로 더 따뜻해져 1입니다. 2일째(75)는 6일째(76)까지 기다려야 해서 4입니다. 6·7일째는 더 따뜻한 날이 없어 0입니다.
예 3 — 계속 추워지기만 하므로 전부 0입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(T: int[]) → int[]
Constraints
Expected complexity
- Time
- O(N)
- Space
- O(N)
Examples
| T | Expected |
|---|---|
[73,74,75,71,69,72,76,73] | [1,1,4,2,1,1,0,0] |
[30,40,50,60] | [1,1,1,0] |
[60,50,40] | [0,0,0] |
Hint
Hint
관점을 뒤집어 보세요. "각 날이 미래를 내다본다"가 아니라, 새 날이 올 때마다 "나보다 추웠고 아직 답을 못 찾은 과거의 날들"에게 내가 답이라고 알려준다고 생각하면 됩니다.
아직 답을 못 찾은 날들을 모아두면, 그 목록은 항상 먼저 온 날일수록 기온이 높은 상태로 유지됩니다. 뒤에 온 날이 더 높았다면 들어올 때 앞의 날들을 이미 처리했을 테니까요.
그래서 가장 최근 것부터 확인하고 꺼내면 됩니다. 넣고 꺼내는 쪽이 같으니 스택이고, 거리를 구해야 하니 스택에는 기온이 아니라 인덱스를 담습니다.
for 안에 while이 있지만, 각 인덱스가 정확히 한 번 들어가고 최대 한 번 나오므로 전체 입니다.
복잡도 목표
각 날마다 뒤쪽을 다시 훑는 풀이는 효율성 테스트에서 시간 초과가 납니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 4 | verdict only |