Funcia
Lv.2arraymonotonic-stackstack

더 따뜻한 날까지

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

정수 배열 T가 주어집니다. T[i]는 i일째의 기온입니다.

각 날에 대해, 자기보다 기온이 높은 날이 처음 오기까지 며칠을 기다려야 하는지 담은 배열을 반환하세요. 그런 날이 없으면 0입니다.

입출력 예

Tresult
[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

  • 1≤N≤200,0001 \le N \le 200{,}000
  • −109≤T[i]≤109-10^9 \le T[i] \le 10^9

Expected complexity

Time
O(N)
Space
O(N)

Examples

TExpected
[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이 있지만, 각 인덱스가 정확히 한 번 들어가고 최대 한 번 나오므로 전체 O(N)O(N) 입니다.

복잡도 목표

각 날마다 뒤쪽을 다시 훑는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.