Funcia
Lv.2greedyheappriority-queue

벽돌과 사다리로 가장 멀리

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

지붕 위를 달리는 파쿠르 선수가 일렬로 늘어선 건물 NN채를 왼쪽부터 차례로 건너려고 합니다. i번 건물의 높이는 heights[i]이고, 선수는 0번 건물 옥상에서 출발합니다.

i번 건물에서 i+1번 건물로 건너갈 때,

  • 다음 건물이 같거나 낮으면 그냥 건너갑니다.
  • 다음 건물이 더 높으면 높이 차 heights[i+1] - heights[i]만큼의 벽돌을 쌓거나, 사다리 하나를 써야 합니다.

가진 벽돌은 bricks개, 사다리는 ladders개이며 한 번 쓴 벽돌과 사다리는 다시 쓸 수 없습니다. 벽돌과 사다리를 가장 잘 나누어 쓸 때 도달할 수 있는 가장 먼 건물의 번호를 반환하세요.

입출력 예

heightsbricksladdersresult
[4, 2, 7, 6, 9, 14, 12]514
[4, 12, 2, 7, 3, 18, 20, 3, 19]1027
[14, 3, 19, 3]1703

입출력 예 설명

예 1 — 2 → 7(차이 5)에 벽돌 5개, 6 → 9(차이 3)에 사다리를 쓰면 4번 건물까지 갑니다. 9 → 14는 차이가 5인데 남은 것이 없습니다.

예 2 — 4 → 12와 3 → 18에 사다리를, 2 → 7에 벽돌 5개를 쓰면 18 → 20에 벽돌 2개를 더 써서 7번 건물까지 갑니다. 3 → 19는 벽돌이 3개뿐이라 갈 수 없습니다.

예 3 — 3 → 19(차이 16)에 벽돌 16개를 쓰면 마지막 건물까지 갑니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(heights: int[], bricks: int, ladders: int) → int

제한 사항

  • 1≤N=1 \le N = heights.length ≤200,000\le 200{,}000
  • 1≤1 \le heights[i] ≤106\le 10^6
  • 0≤0 \le bricks ≤109\le 10^9
  • 0≤0 \le ladders ≤N\le N

기대 복잡도

시간
O(N log N)
공간
O(N)

입출력 예

heightsbricksladders기대 출력
[4,2,7,6,9,14,12]514
[4,12,2,7,3,18,20,3,19]1027
[14,3,19,3]1703

힌트

힌트

어떤 지점까지 갈 수 있는지는 "지금까지 올라간 높이 차들 중 가장 큰 ladders개에는 사다리를, 나머지에는 벽돌을 쓰는 것"으로 판단할 수 있습니다. 사다리는 높이 차와 상관없이 한 번에 해결하므로 큰 차이에 쓰는 것이 이득이기 때문입니다.

매번 지금까지의 높이 차를 정렬해 확인하면 O(N2log⁡N)O(N^2 \log N)이 됩니다. 대신 사다리를 쓴 높이 차들을 최소 힙에 담아 두세요.

  • 오르막을 만나면 일단 사다리를 쓴 것으로 하고 힙에 넣습니다.
  • 힙 크기가 ladders를 넘으면, 힙에서 가장 작은 차이를 꺼내 벽돌로 바꿉니다.
  • 벽돌이 모자라면 바로 그 직전 건물이 답입니다.

전체 O(Nlog⁡N)O(N \log N)입니다.

언어별 시간 제한

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

테스트 그룹

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

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