Funcia
Lv.1array

바다가 보이는 건물

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

해안 도로를 따라 건물이 한 줄로 서 있고, 바다는 줄의 오른쪽 끝 너머에 있습니다. 배열 heights는 왼쪽부터 차례로 건물의 높이입니다.

어떤 건물의 오른쪽에 있는 모든 건물이 그 건물보다 낮으면 그 건물에서 바다가 보입니다. 높이가 같은 건물이 오른쪽에 있으면 바다가 가려집니다. 가장 오른쪽 건물에서는 항상 바다가 보입니다.

바다가 보이는 건물의 번호(0부터 시작)를 오름차순으로 담은 배열을 반환하세요.

입출력 예

heightsresult
[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[]

제한 사항

  • 1≤1 \le heights.length ≤200,000\le 200{,}000
  • 1≤1 \le heights[i] ≤109\le 10^9

기대 복잡도

시간
O(N)
공간
O(1) extra

입출력 예

heights기대 출력
[4,2,3,1][0,2,3]
[1,3,2,4][3]
[5,5,5][2]

힌트

힌트

"오른쪽 건물이 모두 낮다"는 말은 오른쪽 건물들 중 가장 높은 건물보다 높다는 뜻입니다.

그러니 오른쪽 끝에서부터 왼쪽으로 훑으면서 지금까지 본 최대 높이 하나만 기억하면 됩니다. 현재 건물이 그 최댓값보다 높으면 바다가 보이는 건물이고, 최댓값을 갱신합니다.

오른쪽부터 모았으므로 마지막에 결과를 뒤집어 오름차순으로 만드세요.

복잡도 목표

건물마다 오른쪽 건물을 전부 확인하면 O(N2)O(N^2)으로 시간 초과입니다. 오른쪽부터 한 번 훑으면 O(N)O(N)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251350 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.