<Medium> Container With Most Water (LeetCode : C#)

https://leetcode.com/problems/container-with-most-water/

📕 문제 설명

n개의 높이 가지고 있는 정수 배열이 주어진다. 이때 n개의 선이 그려지는데 i번째 선은 (i,0) 부터 (i, height[i]) 형태로 그려진다.

가장 많은 물을 담을 수 있는 두 선을 찾아 컨테이너가 포함할 수 있는 최대 물의 양을 반환해야한다.

• Input
  선의 높이를 담은 정수 배열

• Output
  컨테이너가 담을 수 있는 최대 물의 양

예제

풀이

시도 1.

실패 Brute Force O(N^2)

제일 먼저 떠오른 건 첫 케이스부터 뒤에 막대 하나씩 보면서 가장 큰 area를 찾는 방식이다. 예상대로 시간 초과 ^^..

public class Solution {
    public int MaxArea(int[] height) {
        
        int currentHeight = 0;
        int currentArea = 0;
        int maxArea = 0;

        for (int i = 0; i < height.Length; i++)
        {
            for (int j = i + 1; j < height.Length; j++)
            {
                currentHeight = Math.Min(height[i], height[j]);
                currentArea = currentHeight * (j - i);
                maxArea = maxArea > currentArea ? maxArea : currentArea;
            }
        }

        return maxArea;
        
    }
}

시도 2.

위랑 비슷한데 왼쪽에서부터 확인할 때 현재 길이를 저장한다. 해당 길이보다 짧은 뒤의 케이스는 볼 필요가 없어 넘기는 방식이다.

public class Solution {
    public int MaxArea(int[] height) {
        
        int currentHeight = 0;
        int currentMaxHeight = 0;
        int currentArea = 0;
        int maxArea = 0;

        for (int i = 0; i < height.Length; i++)
        {
            if (currentMaxHeight < height[i])
            {
                currentMaxHeight = height[i];
                for (int j = i + 1; j < height.Length; j++)
                {
                    currentHeight = Math.Min(currentMaxHeight, height[j]);
                    currentArea = currentHeight * (j - i);
                    maxArea = maxArea > currentArea ? maxArea : currentArea;
                }
            }
        }

        return maxArea;
        
    }
}

시도 2. 결과

시도 3.

시도 2보다 개선할 수 있는 방식이다.

1. 왼쪽이랑 오른쪽 포인터를 두고 maxArea 값을 구한다.
2. 왼쪽이랑 오른쪽 중 더 짧은 부분의 포인터를 한 칸 이동한다.
3. 위의 과정을 반복하며 maxArea를 계속 업데이트 해서 가장 큰 Area 값을 반환한다.

public class Solution {
    public int MaxArea(int[] height) {

        int left = 0;
        int right = height.Length - 1;
        int currentHeight = 0;
        int maxArea = 0;


        while (left < right)
        {
            currentHeight = Math.Min(height[left], height[right]);
            maxArea = Math.Max(maxArea, currentHeight * (right - left));

            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }

        }

        return maxArea;
        
    }
}

시도 3. 결과

(시간 복잡도는 해당 풀이부터는 다 150ms~ 대라서 비슷하다고 보면 된다.)