Today's Algorithm(2018-11-27)

leetcode 11. Container With Most Water

어제 손쉽게 풀었던 문제인데요. 문제를 풀고나서 효율성은 거의 빵점이더라구요. 그래서 오늘 다른 사람의 코드를 참고하면서 기존의 코드를 개선할 수 있는 방법을 찾으려 노력하였습니다. 어제 다른 사람의 코드를 봤었을 때는 잘 이해가 안갔는데 넉넉하게 여유를 잡고 보니 알겠더라구요. 그래서 기존 코드와 오늘 참고한 코드에 대해 모두 정리해보려 합니다.

 

처음에 문제를 봤을 때 가장 처음 든 생각은 막대기가 index값을 가지고 있으면서도 height를 가지고 있어야 하기 때문에 Stick이라는 클래스를 만들면 좋겠다는 것이었습니다. 그리고 for문 2개를 이용하여 다른 막대기를 2개를 골라 물의 양을 구하고, 기존 최대 물의 양과 비교하는 것입니다. 정말 단순하죠. 코드를 다음과 같습니다.

class Solution {
    public int maxArea(int[] height) {
        List<Stick> sticks = new ArrayList<>();
        int length = height.length;
        int answer = 0;
        for (int i = 0; i < length; i++) {
            Stick stick = new Stick(i, height[i]);
            sticks.add(stick);
        }

        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                int width = Math.abs(sticks.get(i).index - sticks.get(j).index);
                int level = Math.min(sticks.get(i).height, sticks.get(j).height);
                answer = Math.max(answer, width * level);
            }
        }

        return answer;
    }
}

class Stick {
    int index;
    int height;

    public Stick(int index, int height) {
        this.index = index;
        this.height = height;
    }
}

이렇게 제출하니 답은 맞았지만 Runtime은 1081ms였습니다. 빠른 사람의 코드가 4ms가 나온 것에 비교하면 제가 엄청 비효율적으로 짠 것입니다. 지금은 O(n^2)의 복잡도를 가지는데 좀 더 빠른 방법을 찾아야 했습니다. 그리고 O(n)으로도 풀 수 있다는 것을 알게되었습니다.

 

가장 많은 양을 얻기 위한 몇 가지 사실을 알면 쉽게 답에 접근할 수 있습니다.

1. 너비와 높이는 왠만하면 최대가 되어야 합니다.
2. 높은 값을 만나면 그 값은 최대한 유지하고 다른 값을 변동시켜야 합니다.

 

위와 같이 답에 접근하기 위해선 index를 나타내는 2개의 변수(left, right)가 필요했습니다. 이 변수를 통해 이제 그 물의 양이 최대가 되도록 계속 변동시켜주는 것이죠. 과정은 다음과 같습니다.

• left는 0, right는 맨 오른쪽 인덱스로 지정합니다.
• while(left < right)를 통해 O(n)만큼 돌게끔 합니다.
• 문제에 주어진 규칙에 맞게 left, right가 가리키는 막대기 중 작은 숫자를 높이로 하고, 그 값에 너비를 곱해 최대 물의 양을 갱신합니다.
• 다음번은 left, right가 가리키는 막대기 중 작은 높이가 인덱스 바꾸도록 합니다. left가 작으면 증가, right가 작으면 감소가 되겠죠?

코드로 나타내면 다음과 같습니다.

public class Solution2 {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxHeight = 0;
        int answer = 0;
        while(left < right) {
            maxHeight = Math.min(height[left], height[right]);
            answer = Math.max(answer, (right - left) * maxHeight);

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

        return answer;
    }
}

순차적으로 접근하는 index라 굳이 Stick과 같은 클래스를 만들지 않아도 주어진 배열을 이용하여 접근할 수가 있네요. left와 right를 두어 인덱스를 접근할 수 있게한다는 것! 전에도 이렇게 하여 슬기롭게 푼 방법을 보고 따라해본 것 같은데 생각처럼 머리에 잘 떠오르지 않네요. 두번째 코드처럼 하면 7ms로 이전 코드에 비해 154배 빠르게 풀 수 있네요...