[LeetCode] 11. Container With Most Water 최적화 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Container With Most Water

---

 
문제 요약 (Container with Most Water)

높이 배열에서 두 막대를 선택해 만들 수 있는 “가장 큰 물 담는 용기 넓이”를 구하는 문제

 
문제링크: https://leetcode.com/problems/container-with-most-water
 
 
이 문제는 비교적 쉽게 풀었다. 
가장 큰 넓이가 되려면 가로 × 세로 값이 최대가 되면 된다. 가로 길이는 두 막대 사이 거리이고, 세로 길이는 두 막대 중 더 낮은 높이다.
 
우선, 세로 길이는 배열이 정렬되어 있지 않으니 어디가 최적인지 단번에 알 수 없다. 하지만 가로 길이는 가장 긴 경우가 양 끝 점이므로, 양 끝에서 시작해서 점점 좁혀가면서 최적의 높이를 찾아가면 되겠다고 생각했다.

 

---

💡 핵심 아이디어

 

이 접근이 바로 Two Pointers + Greedy 전략이다.

• 초기 포인터: left = 0, right = n-1
• 현재 넓이 계산
  width = right - left
  height = min(height[left], height[right])
• 넓이 후보 갱신
  • ❗ 중요 포인트
    물 높이는 낮은 막대에 의해 결정되므로 → 항상 더 낮은 쪽 포인터를 이동해야 한다
    (높은 쪽을 움직여봤자 높이는 유지되거나 더 낮아질 확률이 큼)

결과적으로

• Brute Force: 모든 조합 비교 → O(n²)
• Two Pointer: 양 끝에서 한 번씩만 움직임 → O(n)
• 추가 메모리 없음 → O(1)

 

---

코드 (Java)

class Solution {

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

    while (left < right) {
      int width = right - left;
      int minHeight = Math.min(height[left], height[right]);
      maxArea = Math.max(width * minHeight, maxArea);
      if (minHeight == height[left]) {
        left++;
      } else {
        right--;
      }
    }
    return maxArea;
  }
}

 

 

📈 Time / Space Complexity

• 시간: O(n)  
• 공간:  O(1)

이 코드만으로도 충분히 빠르고 정답 처리되며, 투포인터의 핵심 아이디어를 잘 반영하고 있다.

---

🔍 그런데… 더 빠른 코드가 있었다!

 

코드 제출 후 다른 사람 코드를 보니, 같은 투 포인터 방식이지만
불필요한 비교를 더 줄여 성능을 최적화한 버전이 있었다.

핵심 차이:

• 현재 높이보다 작거나 같은 값은 굳이 다시 비교할 필요 없음
• 따라서 포인터를 “한 칸만” 이동하는 대신→ 현재 높이보다 큰 후보를 만날 때까지 연속 스킵

최적 코드

class Solution {
    public int maxArea(int[] a) {
       int l = 0;
       int r = a.length - 1;

       int res = 0; 
       while(l < r){
        int h = Math.min(a[l], a[r]);
        res = Math.max(res, h * (r - l));

        while(a[l] <= h && l < r) l++;
        while(a[r] <= h && l < r) r--;
       }

       return res;
    }
}

 

📈 Time / Space Complexity

• 시간: O(n), 하지만 실제 실행 속도 훨씬 빠름
• 공간:  O(1)

---

 

📝 이번 문제에서 얻은 깨달음

• 문제 구조가 주는 패턴 / 제약 조건 / 본질적인 성질을 이용하자 → 이 문제의 핵심은 “물 높이는 낮은 막대가 결정한다”
• 단순히 큰 값만 찾는 문제가 아니다 → “길이 × 최소 높이”라는 함수 최적화 문제
• 같은 O(n)이라도, “불필요한 비교를 얼마나 덜 하느냐”가 실제 성능을 좌우한다.