Lv.1array
바다가 보이는 건물
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
해안 도로를 따라 건물이 한 줄로 서 있고, 바다는 줄의 오른쪽 끝 너머에 있습니다. 배열 heights는 왼쪽부터 차례로 건물의 높이입니다.
어떤 건물의 오른쪽에 있는 모든 건물이 그 건물보다 낮으면 그 건물에서 바다가 보입니다. 높이가 같은 건물이 오른쪽에 있으면 바다가 가려집니다. 가장 오른쪽 건물에서는 항상 바다가 보입니다.
바다가 보이는 건물의 번호(0부터 시작)를 오름차순으로 담은 배열을 반환하세요.
입출력 예
| heights | result |
|---|---|
[4, 2, 3, 1] | [0, 2, 3] |
[1, 3, 2, 4] | [3] |
[5, 5, 5] | [2] |
입출력 예 설명
예 1 — 1번 건물(높이 2)은 오른쪽의 2번 건물(높이 3)에 가려집니다. 나머지는 모두 오른쪽 건물들보다 높습니다.
예 2 — 가장 오른쪽 건물이 가장 높아서 나머지 건물을 모두 가립니다.
예 3 — 높이가 같은 건물도 바다를 가리므로 마지막 건물만 바다가 보입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(heights: int[]) → int[]
제한 사항
-
heights.length -
heights[i]
기대 복잡도
- 시간
- O(N)
- 공간
- O(1) extra
입출력 예
| heights | 기대 출력 |
|---|---|
[4,2,3,1] | [0,2,3] |
[1,3,2,4] | [3] |
[5,5,5] | [2] |
힌트
힌트
"오른쪽 건물이 모두 낮다"는 말은 오른쪽 건물들 중 가장 높은 건물보다 높다는 뜻입니다.
그러니 오른쪽 끝에서부터 왼쪽으로 훑으면서 지금까지 본 최대 높이 하나만 기억하면 됩니다. 현재 건물이 그 최댓값보다 높으면 바다가 보이는 건물이고, 최댓값을 갱신합니다.
오른쪽부터 모았으므로 마지막에 결과를 뒤집어 오름차순으로 만드세요.
복잡도 목표
건물마다 오른쪽 건물을 전부 확인하면 으로 시간 초과입니다. 오른쪽부터 한 번 훑으면 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1350 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |