Dart-LeetCode 11번: Container With Most Water — 투 포인터 전략으로 풀어보기

물통에 가장 많은 물을 담는 방법은?
LeetCode의 11번 문제 "Container With Most Water"는 그리디한 사고와 투 포인터 알고리즘을 적절히 활용할 수 있는 대표 문제입니다.

이 글에서는 Dart로 문제를 풀이하며,
왜 투 포인터가 최적인지,
어떻게 중복 계산 없이 최대값을 구하는지
명확히 설명합니다.

---

📘 문제 요약

• height[i]는 위치 i에서 세운 수직선의 높이입니다.
• 두 선을 골라, 그 사이를 x축으로 막아 생기는 컨테이너의 물 저장 용량을 구해야 합니다.
• 조건: 컨테이너는 기울일 수 없습니다.

---

🚀 핵심 아이디어: 투 포인터 (Two Pointers)

❌ 브루트 포스 접근 (비효율)

int max = 0;
for (int i = 0; i < height.length; i++) {
  for (int j = i + 1; j < height.length; j++) {
    int area = (j - i) * min(height[i], height[j]);
    max = max > area ? max : area;
  }
}

• 시간 복잡도: O(n²)
• → 모든 경우를 비교 = 너무 느림!

---

✅ 최적화: 투 포인터 전략

import 'dart:math';

class Solution {
  int maxArea(List<int> height) {
    int left = 0, right = height.length - 1, answer = 0;

    while (left < right) {
      int width = right - left;
      int water = width * min(height[left], height[right]);
      answer = max(answer, water);

      if (height[left] < height[right]) {
        left++;  // 더 낮은 쪽을 안쪽으로 이동
      } else {
        right--;
      }
    }

    return answer;
  }
}

---

💡 왜 투 포인터인가?

• 물의 양 = 너비 × 높이
• 너비는 왼쪽/오른쪽 포인터 거리
• 높이는 둘 중 더 낮은 벽이 기준
• 더 높은 벽은 바꾸지 않고, 낮은 벽을 바꿔야 더 나은 결과 가능

→ 즉, 낮은 쪽을 안쪽으로 이동시키며 최댓값 갱신

---

🧪 예제 설명

입력: [1,8,6,2,5,4,8,3,7]
→ 최댓값은 49: height[1]=8, height[8]=7, 거리 7 → 7 × 7 = 49

---

⏱ 복잡도 분석

구분 복잡도

시간	O(n) — 포인터 한 번씩만 움직임
공간	O(1) — 추가 배열 없이 변수만 사용

---

✨ 실전 팁

• 이 문제는 투 포인터 개념을 익히기에 아주 좋아요.
• 리스트의 양 끝에서 출발하여, 내려오면서 갱신하는 방식은 다양한 문제에 응용 가능
• 슬라이딩 윈도우 / 그리디 문제에서도 자주 등장하는 패턴입니다.

---

🏁 마무리

"Container With Most Water"는 단순해보이지만,
투 포인터의 본질적인 사고법을 배울 수 있는 문제입니다.
이 문제 하나만 확실히 이해해도, 이후 LeetCode 문제에서 유사 패턴을 빠르게 인식하게 됩니다.