리트코드 - 11. Container With Most Water

리트코드 - 11. Container With Most Water

출처 - https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

당신은 길이가 n인 정수 배열 height를 가지고 있습니다. 여기서, i번째 선은 (i, 0)과 (i, height[i]) 두 점을 연결하는 수직선으로 그려집니다.
x축과 함께 컨테이너를 형성하는 두 선을 찾아서, 해당 컨테이너가 가장 많은 물을 담을 수 있도록 합니다.
컨테이너가 저장할 수 있는 최대 물의 양을 반환하세요.

컨테이너를 기울일 수는 없다는 점에 유의하세요.

 

의사코드

left = 0 right = height.length - 1 maxWater = Integer.MIN_VALUE 반복문 시작 (left < right)     lowHeight = Math.min(height[left], height[right])     curWater = (right - left) * lowHeight     if (curWater > maxWater)         maxWater = curWater     반복문 시작 (left < right && height[left] <= lowHeight)         left += 1     반복문 종료     반복문 시작 (left < right && height[right] <= lowHeight)         right -= 1     반복문 종료 반복문 종료 maxWater 리턴

 

풀이코드

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxWater = Integer.MIN_VALUE;

        while (left < right) {
            int lowHeight = Math.min(height[left], height[right]);
            int curWater = (right - left) * lowHeight;
            if (curWater > maxWater) {
                maxWater = curWater;
            }
            while (left < right && height[left] <= lowHeight) {
                left++;
            } 
            while (left < right && height[right] <= lowHeight) {
                right--;
            }
        }

        return maxWater;
    }
}

 

코드설명

이전에 물을 채우는 Trapping-Rain-Water(해결 포스팅)와 비슷한 문제다.

두 개의 막대를 기준으로 삼아서 제일 양끝 막대를 선택하여 담을 수 있는 물을 확인하면 된다.

두 막대를 각각 left와 right로 두는 투포인터 접근 방법이 좋을 것 같다.

 

담을 수 있는 물의 양은 가로는 막대의 거리만큼, 세로는 '작은 막대의 길이'만큼 담을 수 있고, 담는 양은 가로 x 세로일 것이다.

그럼 이제 해야 할 일은 두가지이다.

 

1. 두 개의 막대 중 작은 막대를 기준으로 하여 이것보다 작거나 같으면 큰 막대를 찾아 여행을 떠나야 한다.

2. 최대로 담을 수 있는 물의 양을 비교한다.

 

가장 바깥쪽 반복문에서는 투 포인터를 이동시키는 일만 한다.

먼저 두 개의 막대중 작은 막대의 길이를 lowHeight에 저장하고, 물의 양을 계산하여 curWater에 저장한다.

이 때 maxWater보다 curWater가 많다면 maxWater에 담아주면 된다.

if문을 쓰지 않고 Math.max(curWater, maxWater)도 좋겠다.

 

이제 lowHeight보다 큰 막대를 찾는 것을 반복하는데, 두 개의 while문을 사용했다.

현재 포인터의 막대가 lowHeight보다 작거나 같으면 이동시키는 것이다.

 

이 경우는 left 막대가 작은경우, right 막대가 작은경우, 두 막대가 같은 경우 움직임이 다르다.

첫번째로 left 막대가 lowHeight보다 작다면 첫번째 while문에 의해서만 left 포인터가 이동하며 lowHeight보다 큰 막대를 찾는다.

두번째로는 반대로 right 포인터만 움직인다.

두 막대가 같은 경우 둘다 가운데로 움직이며 큰 막대를 찾는다.

 

세가지 경우 모두 막대를 찾다보면 left가 right보다 커지는 순간이 있으므로 추가 조건을 달아주었다.

 

이렇게 번거롭게 한 이유는 아래 초기코드를 보면 된다.

단순히 오른쪽과 왼쪽 막대를 비교하여 포인터를 이동하면, 하나씩 포인터를 이동하며 수많은 lowHeight와 curWater를 구해야 한다.

따라서 while문 내에서 포인터를 계속 이동시켜서 연산 횟수를 줄인 것이다.

 

초기코드의 런타임은 5ms(9%) 였고, 풀이코드의 런타임은 1ms(100%)로 개선되었다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

 

문제를 풀며 생각한 흐름과 배운 점

초기코드

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxWater = Integer.MIN_VALUE;

        while (left < right) {
            int lowHeight = Math.min(height[left], height[right]);
            int curWater = (right - left) * lowHeight;
            if (curWater > maxWater) {
                maxWater = curWater;
            }
            if (height[left] < height[right]) {
                left++;
            } else if (height[left] >= height[right]) {
                right--;
            }
        }

        return maxWater;
    }
}

요즘 초기 코드는 풀이코드의 참조 정도로만 사용되는 것 같다.

단순히 풀기는 어느정도 빨리 푸는데 개선을 고민하는데 많은 시간이 든다.

 

정 개선 방법이 떠오르지 않으면, 먼저 잘 풀어낸 코드를 보고 완전히 창을 닫은 다음 다시 내 코드를 열어서 직접 구현해본다.

이 방법이 제일 좋은 것 같다.

 

정리

투 포인터의 개선을 이끌어내는 방법.