11. Container With Most Water

🧩 문제 이해

int[] height (length = n)
각 인덱스는 x축 위의 좌표를 나타내며,각 값은 해당 선의 높이를 의미한다.
이 중 두 개의 선을 선택해 만들 수 있는 최대 넓이를 구하는 문제이다.

넓이 = (right - left) × min(height[left], height[right])

💡 아이디어

1️⃣ 첫 번째 접근 (Brute Force)

• 가능한 모든 쌍을 다 계산해보는 방법.
• 하지만, O(n²)이라 비효율적이다.
• n이 커질수록 너무 많은 연산이 필요하다.

그렇다면, 더 효율적으로 구할 수 있는 방법이 없을까?

2️⃣ 두 번째 접근 (Two Pointers)

• 양쪽 끝에서부터 시작한다.
• left = 0, right = n - 1
• 두 선 중 더 짧은 쪽을 한 칸 안쪽으로 이동시킨다. 왜냐하면, 더 긴 쪽을 줄이는 건 넓이를 키울 수 없기 때문이다.
• 이동할 때마다 현재 넓이를 계산하고, 최대값(max)을 갱신한다.
• 이 방식으로 한 번만 배열을 훑으면 되기 때문에 O(n) 으로 해결할 수 있다.

🧮 풀이 코드

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int max = 0;

        while (left != right) {
            max = Math.max(max, Math.min(height[left], height[right]) * (right - left));
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return max;
    }
}

⚙️ 개선 포인트

• while (left < right)이 더 명확하고, !=보다 안전하다.