[Leetcode] 11. Container With Most Water

Identifying the Problem

음이 아닌 정수 a1, a2, ..., a가 각각 좌표(i, ai)의 한 점을 나타내는 경우

x축과 함께 용기에 물이 가장 많이 들어 있는 두 개의 선을 찾아 넓이를 구한다.

Organizing thoughts

O(n²) 으로 가능한 모든 넓이를 구해서 풀 수 있지만, 매우 비효율적이다.

 

간단한 원칙 두가지만 알면 이해하기 쉽다.

1. 가장 작은 기둥기준으로 넓이가 구해진다는 것

2. 가로길이는 조절 수 있지만 세로 길이는 상수값이기에 정할 수 없다는 것

 

즉 가로길이를 조절하면서 가장 큰 넓이를 구하면 된다.

길이가 n이고 가로길이가 n-1일 때 넓이를 구하는 방식은 2가지다.

만약 왼쪽 세로가 오른쪽 보다 더 길다면, 오른쪽의 가로길이만 줄이면 된다.

이런 식으로 왼쪽 오른쪽 비교해가면서 가로길이를 줄여나가며 최대 넓이를 구하면 된다.

 

처음 바로 이 생각을 하기에 너무 어렵다고 느낀다. 

 

여기에 작동원리가 상세히 나와있으니 참고하면 좋을 것 같다.

Yet another way to see what happens in the O(n) algorithm - LeetCode Discuss

1. 양끝에서 시작

2. l과 r중 작은 기둥 찾기

2-1 둘다 같다면 l+1과 r-1을 비교한다.

2-2 작은 기둥과 두 사이 간격을 곱한 값을 합에 대입한다.

3. 합이 max 보다 크면 max 값에 합을 대입한다.

4. 기둥을 비교해 l 또는 r의 인덱스를 가운데로 당긴다.

Sourcecode

int maxArea(int* height, int heightSize)
{
    
  int l = 0;
  int r = heightSize - 1;
  int max = 0;
  int sum = 0;

  if(height[l] > height[r])  
          max = (r-l) * height[r];	
  else 
          max = (r-l) * height[l];	   

  while(l != r)
  {
      if(height[l] > height[r])  
      {
          sum = (r-l) * height[r];
          r--;	
      } 

      else if(height[l] < height[r])  
      {
          sum = (r-l) * height[l];
          l++;	
      } 
      else 
      {
          sum = (r-l) * height[l];

          if(height[l+1] > height[r-1])
              r--;
          else 
              l++;

      }

      if(sum > max) max = sum;
  }

      return max;
}