LeetCode Q - Container With Most Water (Java)

February LeetCoding Challenge 2021 ( Week 3, day 17 )

Q : Container With Most Water

---

문제 해설

 

길이가 n인 음수가 아닌 정수형 배열 height의 각각의 원소의 인덱스와 원소 값은 좌표 (i, ai)를 이룬다.

좌표위에는 길이가 (i,ai) - (i,0) 인 n개의 수직선들이 그려진다.

두 개의 수직선을 골라 물을 담을 수 있는 컨테이너를 만들 수 있는데, 물을 최대한 많이 담을 수 있는 컨테이너가 생성되는 두 개의 수직선을 골라라.

 

---

 

제한 사항

- n == height.length    

- 2 <= n <= 3 * 10^4

- 0 <= height[i] <= 3 * 10^4

 

---

문제 풀이

단순 무식하게 이중 포문을 만들어 해결할 수도 있지만,

Two pointer method 를 이용하는 더 효율적인 방법이 존재합니다.

 

 

1. 배열의 첫 번째 인덱스를 가리키는 포인터 pl , 배열의 마지막 인덱스를 가리키는 포인터 pr, 물을 담는 컨테이너의 넓이를 저장할 변수 max_contain 를 준비합니다.

 

2. 첫 번째 원소와 마지막 원소를 수직선으로 하는 컨테이너가 담을 수 있는 물의 넓이를 저장합니다.

 

3. pl 이 가리키는 원소가 pr 이 가리키는 원소보다 작다면 pl을 오른쪽으로 이동시킵니다.

   더 크다면, pr을 왼쪽으로 이동시킵니다.

 

4. 바뀐 수직선으로 생성한 컨테이너의 넓이가 이전에 만들어진 컨테이너의 넓이보다 크다면 바꿉니다.

 

5. 3번, 4번 과정을 pl > pr 되기 전까지 반복합니다.

 

 

- java 코드

 

보기가 좀 안 좋군요

 

class Solution {
    public int maxArea(int[] height) {
        int pl = 0 , pr = height.length - 1 , max_contain = 0;
        do {
            max_contain = Math.max(max_contain, (pr - pl) * Math.min(height[pr], height[pl]));
            if (height[pl] < height[pr]) {
                pl++;
            } else
                pr--;
        } while(pl < pr);
        return max_contain;
    }
}

 

 

결과

Runtime : 2 ms , beats 96.04% of java submissions

Memory Usage : 40.3 MB , beats 88.44% of java submissions

 

수행 시간 : 2 ms, 상위 약 4%

메모리 사용량 : 40.3 MB, 상위 11.6%

 

최상위권 메모리 사용량도 39.6 MB인것을 감안하면 준수한 결과인것 같습니다.

 

 

 

결론

 

단순 무식법 (brute force)이 능사는 아닙니다.