[JAVA] LeetCode - Container With Most Water - 11

문제내용

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

Container With Most Water - LeetCode

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

---

문제 접근 방법

막대기 두개사이에 채워질수 있는 물의 양 중에서 최댓값을 구하는 문제다.

이 문제에서 완전탐색을 할경우 O(N^2)이 걸리게 되는데 N이 최대 10^5 이기 때문에 시간초과가 날꺼라고 생각을 했고, 특정 값을 찾기 위한 방법으로 예전에 사용했던 '투 포인터' 알고리즘이 생각났다.

 

투포인터 알고리즘의 원리는 두가지가 있는데

첫번째는 slowPointer, fastPointer 두개의 변수를가지고 인덱스 0부터 시작해서 탐색하는 방법과

두번째는 startPointer, endPointer 두개의 변수를가지고 인데스 0과 끝에서 시작해 탐색하는 방법이 있다.

그리고 나는 두번째 방법으로 풀었고 로직은 아래와 같다.

1. 작은 막대기 기준
   문제를 잘 살펴보면 물이 채워질 수 있는 조건은 결국 두개의 막대기중 작은막대기의 높이만큼 채울수 있다. 이를 다시 생각하면 결국 물을 한번 채우고 두개의 막대기 중 더 작은 막대기의 인덱스를 하나 옮김으로써 더 긴막대기를 찾을수 있도록 한다. 한마디로 옮겨지 포인터 변수로 하여금 가장 큰 값을 갖도록 하는 작업이다.
2. 반복
   1번에서 막대기를 옮기는 과정을 설명했다. 1번에서 처럼 막대기를 옮기고 물의 양을 비교하고 다시 옮기고 비교하고를 반복한다. 언제까지? startPointer가 endPointer보다 커지는 순간까지. 즉, 두개의 포인터가 만나는 순간까지 막대기를 계속해서 옮긴다. 두 포인터가 만났다는 뜻은 모든 막대기의 탐색을 마쳤다는 의미가 된다.

투포인터 로직으로 풀게되면 O(N)의 시간 복잡도가 걸리기 때문에 무난하게 통과가능하다.

 

---

풀이

public class Solution {
    public static int maxArea(int[] height) {
    	int max = 0;//최댓값
    	int start = 0;//시작 포인터
    	int end=height.length-1;//끝 포인터
    	while(start<end){//변수두개 만나는 순간까지
    		int w = end-start;//가로길이
    		int h = Math.min(height[start], height[end]);//세로길이(더작은 막대기 기준)
    		max = Math.max(max, w*h);//최댓값 갱신
    		
    		//더작은 막대기를 옮기는 과정
    		if(height[start]>=height[end]) end--;
    		else start++;
    	}
        
    	return max;
    }
}

---

마치며

투 포인터 알고리즘을 숙지하고 있고, 문제에서 '결국 작은 막대기 기준으로 물을 채운다.' 라는 조건을 알아챌수 있다면 수월하게 풀수 있는 문제라고 생각한다.