Funcia
Lv.2arraygreedytwo-pointers

가장 많은 물을 담는 벽

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

정수 배열 A가 주어집니다. A[i]는 i번 자리에 세운 벽의 높이입니다.

서로 다른 두 자리 i < j를 골라 물을 담을 때, 담기는 물의 양은

min⁡(A[i], A[j])×(j−i)\min(A[i],\ A[j]) \times (j - i)

입니다. 담을 수 있는 물의 최대량을 반환하세요.

입출력 예

Aresult
[1, 8, 6, 2, 5, 4, 8, 3, 7]49
[1, 1]1
[4, 3, 2, 1, 4]16

입출력 예 설명

예 1 — 1번(8)과 8번(7)을 고르면 min⁡(8,7)×7=49\min(8,7) \times 7 = 49 입니다.

예 3 — 0번(4)과 4번(4)을 고르면 4×4=164 \times 4 = 16 입니다.

효율성

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

함수 시그니처

solution(A: int[]) → long

제한 사항

  • 2≤N≤200,0002 \le N \le 200{,}000
  • 0≤A[i]≤1090 \le A[i] \le 10^9
  • 답은 64비트 정수 범위입니다.

기대 복잡도

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

입출력 예

A기대 출력
[1,8,6,2,5,4,8,3,7]49
[1,1]1
[4,3,2,1,4]16

힌트

힌트

양 끝에서 시작하세요. 그 상태가 거리가 가장 먼 조합입니다. 여기서 좁혀가면 거리는 반드시 줄어드니, min⁡\min 값이 커질 가능성에만 기대야 합니다.

A[lo] < A[hi]라고 해봅시다. hi를 당겨도 min⁡\min은 여전히 A[lo] 이하라 거리만 줄어 무조건 손해입니다. 반대로 lo를 밀면 min⁡\min이 커질 수 있습니다.

그러니 낮은 쪽을 움직이세요. 이때 버려지는 쪽은 "그 벽을 포함하는 조합 중 최선"을 이미 계산한 상태이므로 손해가 없습니다.

순서가 중요합니다. 현재 상태로 답을 먼저 갱신하고, 그다음에 포인터를 움직이세요. 안 그러면 가장 먼 조합을 한 번도 평가하지 않습니다.

복잡도 목표

모든 쌍을 확인하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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