Lv.2arraygreedytwo-pointers
가장 많은 물을 담는 벽
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
정수 배열 A가 주어집니다. A[i]는 i번 자리에 세운 벽의 높이입니다.
서로 다른 두 자리 i < j를 골라 물을 담을 때, 담기는 물의 양은
입니다. 담을 수 있는 물의 최대량을 반환하세요.
입출력 예
| A | result |
|---|---|
[1, 8, 6, 2, 5, 4, 8, 3, 7] | 49 |
[1, 1] | 1 |
[4, 3, 2, 1, 4] | 16 |
입출력 예 설명
예 1 — 1번(8)과 8번(7)을 고르면 입니다.
예 3 — 0번(4)과 4번(4)을 고르면 입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(A: int[]) → long
Constraints
- 답은 64비트 정수 범위입니다.
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| A | Expected |
|---|---|
[1,8,6,2,5,4,8,3,7] | 49 |
[1,1] | 1 |
[4,3,2,1,4] | 16 |
Hint
Hint
양 끝에서 시작하세요. 그 상태가 거리가 가장 먼 조합입니다. 여기서 좁혀가면 거리는 반드시 줄어드니, 값이 커질 가능성에만 기대야 합니다.
A[lo] < A[hi]라고 해봅시다. hi를 당겨도 은 여전히 A[lo] 이하라 거리만 줄어 무조건 손해입니다. 반대로 lo를 밀면 이 커질 수 있습니다.
그러니 낮은 쪽을 움직이세요. 이때 버려지는 쪽은 "그 벽을 포함하는 조합 중 최선"을 이미 계산한 상태이므로 손해가 없습니다.
순서가 중요합니다. 현재 상태로 답을 먼저 갱신하고, 그다음에 포인터를 움직이세요. 안 그러면 가장 먼 조합을 한 번도 평가하지 않습니다.
복잡도 목표
모든 쌍을 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |