문제 바로가기

Python

O(nlogn)

처음 생각

1. 정렬
2. 가장 긴 두 위치에서 시작해서 점점 작은 위치를 탐색
   2.1 만약 높이를 줄이는게 더 이득이면 수정

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # index sort
        sortedIndices= sorted(range(len(height)), key=lambda k: height[k], reverse=True)
        
        if sortedIndices[0] < sortedIndices[1]:
            idxL, idxR = sortedIndices[0], sortedIndices[1]
        else:
            idxL, idxR = sortedIndices[1], sortedIndices[0]
        
        currentH = min(height[idxL], height[idxR])
        
        sortedIndices = sortedIndices[2:]
        for idx in sortedIndices:
            if idx < idxL:
                if self.isPlus(idxR-idxL, idxL-idx, height[idx], currentH - height[idx]):
                    idxL = idx
                    currentH = height[idx]
            elif idxR < idx:
                if self.isPlus(idxR-idxL, idx-idxR, height[idx], currentH - height[idx]):
                    idxR = idx
                    currentH = height[idx]
        
        return (idxR - idxL) * currentH
                
    def isPlus(self, width, widthDiff, newHeight, heightDiff) -> bool:
        return widthDiff * newHeight > width * heightDiff

그런데 처음에는 손해여서 넘겼던 위치가 나중에 더 이득인데도 이미 지나가서 선택하지 못하는 경우가 생겼다.

testcase: [76,155,15,188,180,154,84,34,187,142,22,5,27,183,111,128,50,58,2,112,179,2,100,111,115,76,134,120,118,103,31,146,58,198,134,38,104,170,25,92,112,199,49,140,135,160,20,185,171,23,98,150,177,198,61,92,26,147,164,144,51,196,42,109,194,177,100,99,99,125,143,12,76,192,152,11,152,124,197,123,147,95,73,124,45,86,168,24,34,133,120,85,81,163,146,75,92,198,126,191]

위의 테스트케이스에서 다음과 같은 순서로 update가 이루어진다.

idxL	idxR	currentH
33	41 -> 53	198
33	53 -> 97	198
33 -> 3	97	198 -> 188

그래서 최종 값은 188 * 94 = 17672가 되지만 이는 오답이다.
오른쪽 인덱스가 97이 아닌 99가 되면 같은 높이를 유지하면서 더 많은 물을 담을 수 있기 때문이다. 하지만 191을 값으로 가지는 99번째 인덱스는 이미 이전 탐색에서 지나가서 비교할 수 없게 된다.
따라서 비교 후에 idxL과 idxR, height을 update하는게 아니라, idxL과 idxR은 계속 확장하되 maxArea를 update하는 방식으로 해결했다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # index sort
        sortedIndices= sorted(range(len(height)), key=lambda k: height[k], reverse=True)
        
        idxL, idxR = sortedIndices[0], sortedIndices[1]
        if idxL > idxR:
            idxL, idxR = idxR, idxL

        sortedIndices = sortedIndices[2:]
        maximumArea = (idxR - idxL) * min(height[idxL], height[idxR])
        
        for i in sortedIndices:
            if i < idxL:
                idxL = i
            elif idxR < i:
                idxR = i
            else:
                continue
            area = (idxR - idxL) * height[i]
            if area > maximumArea:
                maximumArea = area
        
        return maximumArea

O(n)

정렬없이 좌, 우에서 범위를 줄여나가며 탐색한다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        area, maxSoFar = 0, 0
        l, r = 0, len(height) - 1
        
        while l < r:
            if height[l] < height[r]:
                area = (r - l) * height[l]
                l += 1
            else:
                area = (r - l) * height[r]
                r -= 1

            if area > maxSoFar:
                maxSoFar = area
            
        return maxSoFar

Javascript

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    const n = height.length;
    if (n === 2) return Math.min(...height);
    
    let left = 0, right = n - 1;
    let maxSoFar = 0;
    while (left < right) {
        const area = (right - left) * Math.min(height[left], height[right]);
        if (height[left] < height[right]) left++;
        else right--;
        maxSoFar = Math.max(maxSoFar, area);
    }
    
    return maxSoFar;
};