[LeetCode] Container With Most Water

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

Container With Most Water - LeetCode

2021-01-09

---

public class SolutionContainerWithMostWater {
    public static int maxArea(int[] height) {
        int answer = 0;
        // (1) brute force
        for(int i = 0; i < height.length; i++) {
            for(int j = height.length-1; j > i; j--) {
                int tmp = (height[i] < height[j]) ? height[i] : height[j];
                int num = tmp * (j-i);
                if(answer < num) answer = num;
            }
        }
        
        // (2) two pointer
        int start = 0;
        int end = height.length-1;
        while(start < end) {
            answer = Math.max(answer, Math.min(height[start], height[end])*(end-start));
            if(height[start] < height[end]) {
                start++;
            } else {
                end--;
            }
        }
        
        return answer;
    }
 
    public static void main(String[] args) {
 
        int h[] = {1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(h));
    }
}
 

#문제풀이

브루트 포스로 풀었고, 시간이 너무 오래걸려서 솔루션을 봐봤다.

 

(1) Brute-force

브루트포스는 말그대로 두 라인을 잡고 (두 라인 중에 적은 값) * (두 라인 사이의 거리) 중 가장 큰 값을 구하면 된다.

 

(2) two pointer

투 포인터는 start는 시작점에 end는 끝점에 두고, 시작점이 끝점보다 커지기 전까지만 실행한다. height[start] 값이 height[end]값보다 작은 경우는 start 값을 ++ 해주어서 새로운 값을 계산 할 수 있도록 해야한다. 

 

그리고 if문을 시작하기 전에 answer 값을 구하는 이유는 [1,2] 와 같은 경우 if문에 들어가버리면 계산도 못 하고 끝나버리기 때문이다.