다음에 올 더 큰 수
실버 IV의견: 0
기상 관측소에서 \(N\)일 간의 기온을 기록했다. \(i\)번째 날의 기온을 \(t_i\)라 할 때, 각 날마다 그 날보다 기온이 엄밀히 더 높은 날이 몇 일 뒤에 처음으로 오는지 구하여라. 더 높은 날이 없으면 \(0\)을 출력한다.
즉, \(i\)번째 날에 대해 \(i < j\)이고 \(t_j > t_i\)인 가장 작은 \(j\)를 찾아 \(j - i\)를 출력한다. 그러한 \(j\)가 없으면 \(0\)을 출력한다.
- \(1 \le N \le 100\,000\)
- \(1 \le t_i \le 10^9\)
첫째 줄에 날 수 \(N\)이 주어진다.
둘째 줄에 각 날의 기온 \(t_1, t_2, \dots, t_N\)이 공백으로 구분되어 주어진다.
한 줄에 \(N\)개의 정수를 공백으로 구분해 출력한다. \(i\)번째 정수는 \(i\)번째 날에 대한 답이다.
8
73 74 75 71 69 72 76 73
1 1 4 2 1 1 0 0
\(73\)의 다음 더 높은 온도 \(74\)는 \(1\)일 뒤, \(74\)→\(75\)는 \(1\)일 뒤, \(75\)→\(76\)은 \(4\)일 뒤이다. \(76\)보다 높은 온도는 없어 \(0\)이다. \(71\)의 다음 더 높은 온도는 \(72\)(\(2\)일 뒤), \(69\)→\(72\)(\(1\)일 뒤), \(72\)→\(76\)(\(2\)일 뒤), \(73\)은 더 높은 온도 없어 \(0\)이다.
3
3 3 3
0 0 0
모든 온도가 동일하여 더 높은 날이 없으므로 전부 \(0\)이다.
1
5
0
온도가 하나뿐이므로 다음이 없어 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
다음에 올 더 큰 수
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
다음에 올 더 큰 수