C++로 풀어보는 가장 많은 물을 담을 수 있는 컨테이너 문제

문제 소개

컨테이너 벽들의 높이가 담긴 배열이 주어졌을 때, 가장 많은 양의 물을 담을 수 있는 컨테이너를 찾는 것이 목표입니다. 벽의 높이는 배열의 요소로 주어지며, 두 벽 사이의 거리는 너비로 간주합니다.

예를 들어 높이가 Arr[i]와 Arr[j]인 두 벽 사이의 너비는 j-i입니다(단, 0 ≤ i < j ≤ N). 여기서 N은 벽의 개수, 즉 배열의 길이입니다.

물은 두 벽 중 낮은 높이까지만 차오릅니다. 따라서 Arr[i] < Arr[j]라면 물의 높이는 Arr[i]가 되고, 물이 담기는 면적은 다음과 같이 계산할 수 있습니다.

면적 = min(Arr[i], Arr[j]) × (j - i)

이 글에서는 이러한 면적의 최댓값을 구하는 방법을 알아보겠습니다.

예제 1

입력

Arr[] = { 5, 1, 2, 3, 5 }

출력

최대 물 면적 : 20

설명

각 벽 쌍에 대해 계산한 면적은 다음과 같습니다.

Arr[0]과 Arr[4] : 너비 4, 면적 = min(5, 5) × 4 = 20
Arr[0]과 Arr[3] : 너비 3, 면적 = min(5, 3) × 3 = 9
Arr[0]과 Arr[2] : 너비 2, 면적 = min(5, 2) × 2 = 4
Arr[1]과 Arr[4] : 너비 3, 면적 = min(1, 5) × 3 = 3
Arr[2]와 Arr[4] : 너비 2, 면적 = min(2, 5) × 2 = 4

가장 큰 면적은 20이며, 이때 사용되는 벽은 Arr[0]과 Arr[4]입니다.

예제 2

입력

Arr[] = { 1, 5, 4, 3, 2, 4 }

출력

최대 물 면적 : 16

설명

Arr[0]과 Arr[5] : 너비 5, 면적 = min(1, 4) × 5 = 5
Arr[1]과 Arr[5] : 너비 4, 면적 = min(5, 4) × 4 = 16
Arr[2]와 Arr[5] : 너비 3, 면적 = min(4, 4) × 3 = 12
Arr[1]과 Arr[3] : 너비 2, 면적 = min(5, 3) × 2 = 6
Arr[1]과 Arr[4] : 너비 3, 면적 = min(5, 2) × 3 = 6

가장 큰 면적은 16이며, 이때 사용되는 벽은 Arr[1]과 Arr[5]입니다.

접근 방법: 두 포인터(Two Pointer) 기법

모든 벽 쌍을 일일이 확인하는 브루트포스 방식은 O(N²)의 시간이 걸립니다. 대신 두 포인터 기법을 사용하면 O(N) 시간에 문제를 해결할 수 있습니다.

정수 배열 walls[]에는 벽들의 높이가 저장되어 있습니다.
mostwater(int A[], int len) 함수는 높이 배열과 원소 개수를 받아 가장 많은 물을 담을 수 있는 컨테이너의 면적을 반환합니다.
왼쪽 끝을 가리키는 l = 0과 오른쪽 끝을 가리키는 r = len-1 두 인덱스로 탐색을 시작합니다.
area는 현재 컨테이너의 면적, maxarea는 지금까지 발견한 최대 면적을 저장하며 초기값은 모두 0입니다.
l < r인 동안 반복하면서, 물의 높이는 두 벽 A[l]과 A[r] 중 낮은 값(minwall)이 됩니다.
두 벽 사이의 너비는 인덱스의 차이(r - l)입니다.
현재 면적을 minwall × (r - l)로 계산하고, 기존 최댓값보다 크면 maxarea를 갱신합니다.
그다음 더 낮은 벽 쪽 포인터를 안쪽으로 한 칸 이동합니다. 낮은 벽을 그대로 두면 너비만 줄어들어 면적이 더 커질 수 없기 때문입니다.
반복이 끝나면 maxarea에 가장 많은 물을 담을 수 있는 컨테이너의 면적이 저장됩니다.
maxarea를 결과로 반환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;

int mostwater(int A[], int len){
    int l = 0;         // 컨테이너 왼쪽 벽 인덱스
    int r = len - 1;   // 컨테이너 오른쪽 벽 인덱스
    int area = 0, maxarea = 0;
    int minwall;

    while (l < r){
        // 두 벽 중 낮은 높이가 물의 높이가 됨
        minwall = A[l] <= A[r] ? A[l] : A[r];
        // 면적 = 낮은 벽의 높이 × 너비(r-l)
        area = minwall * (r - l);
        // 최대 면적 갱신
        maxarea = area >= maxarea ? area : maxarea;
        // 더 낮은 벽 쪽 포인터를 안쪽으로 이동
        if (A[l] < A[r])
            l += 1;
        else
            r -= 1;
    }
    return maxarea;
}

int main(){
    int walls[] = {1, 5, 4, 3, 2, 4};
    int num = sizeof(walls) / sizeof(walls[0]);
    cout << endl << "Container with Most water has area:" << mostwater(walls, num);
}

실행 결과

Container with Most water has area:16

마무리

두 포인터 기법을 활용하면 모든 경우를 확인하지 않고도 선형 시간 O(N)에 최대 물 면적을 구할 수 있습니다. 공간 복잡도 역시 O(1)로 매우 효율적이므로, 코딩 테스트 단골 유형인 '가장 많은 물이 담기는 컨테이너' 문제를 학습하기에 좋은 예제입니다.