Portfolio

📑 문제

✏️ 풀이

재영

맨 앞! 맨 뒤!

넓이 계산! 넓이 업데이트!

start end 둘 중 더 짧은 거! 업데이트!


const maxArea = height => {
  let start = 0;
  let end = height.length - 1;
  let maxArea = 0;
  while (start < end) {
    const startHeight = height[start];
    const endHeight = height[end];
      
    let nowMaxArea = getArea(startHeight, endHeight);
    if (maxArea < nowMaxArea) maxArea = nowMaxArea;
      
    if (startHeight < endHeight) start += 1;
    else end -= 1;
  }
    
  function getArea(startHeight, endHeight) {
    return Math.min(startHeight, endHeight) * (end - start);
  }
  return maxArea
}

효성


var maxArea = function(height) {
    let maxArea = 0
    let start = 0
    let end = height.length - 1
    
    while(start < end) {
        const min = height[start] < height[end] ? height[start] : height[end]
        if(maxArea < min * (end - start)) {
            maxArea = min * (end - start)
        }
        height[start] < height[end] ? start++ : end--
    }
    return maxArea
};

투포인터를 이용해 start와 end를 양 끝으로 지정한다.

start가 end보다 커지기 전까지 최소높이를 구한다.

만약 maxArea보다 최소높이에 너비를 곱한 값(넓이)이 더 크면 maxArea를 갱신한다.

이후 더 높은 값과 비교를 위한 연산을 거친다.

최종적으로 maxArea를 반환한다.

💡

two pointer에서 어떻게 왼쪽과 오른쪽을 줄여나갈지에 대한 고민이 더 필요함!

은찬


/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = function(height) {
    let front = 0;
    let back = height.length - 1;
    let answer = 0;
    
    while(front < back){
        let width = 0;
        
        if(height[front] < height[back]){
            width = height[front] * (back - front);
            front++;
        } else{
            width = height[back] * (back - front);
            back--;
        }
        
        answer = answer < width ? width : answer;
    }
    
    return answer;
};

현석


var maxArea = function(height) {
    let idx1 = 0;
    let idx2 = 0;
    let maxheight1 = height[idx1];
    let maxheight2 = height[idx2];
    
    for (let i = 0; i< height.length; i++) {
        if (height[i] >= maxheight1) {
            maxheight2 = maxheight1;
            maxheight1 = height[i];
            idx2 = idx1;
            idx1 = i
        } else if(height[i] >= maxheight2) {
            maxheight2 = height[i];
            idx2 = i
        }
    }
    
    let startIdx = Math.min(idx1, idx2);
    let endIdx = Math.max(idx1, idx2);
    let max = (endIdx - startIdx) * maxheight2;
    
    for(let i = startIdx; i>=0; i--) {
        for(let j = endIdx; j< height.length; j++) {
            const area = getArea(height, i, j)
            max = max < area ? area : max;
        }
    }
    return max
    
};

function getArea(arr, start, end) {
    return (end- start) * Math.min(arr[start], arr[end])
}


Runtime: 8587 ms, faster than 5.01%
Memory Usage: 48 MB, less than 45.76%


두번째 풀이
var maxArea = function(height) {
    let leftIdx = 0;
    let rightIdx = height.length - 1;
    let max = 0
    
    
    while(leftIdx < rightIdx) {
        const area = getArea(height, leftIdx, rightIdx) 
        max = max < area ? area: max;
        
        if(height[rightIdx] > height[leftIdx]) {
            leftIdx++;
        } else {
            rightIdx--;
        }
        
    }
    return max
}

function getArea(arr, start, end) {
    return (end- start) * Math.min(arr[start], arr[end])
}
Runtime: 84 ms, faster than 84.79%
Memory Usage: 48.2 MB, less than 21.44%

가영


var maxArea = function(height) {    
    let start = 0;
    let end = height.length - 1;
    let max = 0;
    
    while (start < end) {
        max = getArea(height, start, end) > max ? getArea(height, start, end) : max;
        
        height[start] < height[end] ? start++ : end--;
    }
    
    return max;
};

function getArea(arr, start, end) {
    return (end- start) * Math.min(arr[start], arr[end])
}

🚫

현석님의 첫번째 풀이 방식으로 리팩토링하려고 시도해보았으나,, 중첩 반복을 없애지 못하고 실패하였습니다🥲 초기 포인터를 중간 지점에 두게 되면 각 포인터를 이동할 때마다 - end 이동 시: 0 ~ 이동한 end까지의 모든 height에 대한 Area - start 이동 시: 이동한 start ~ height.length-1 까지의 모든 height에 대한 Area 를 구하여 비교해야 하는데, 포인터가 중간지점에 위치할수록 비교 횟수가 많아지기 때문에 성능적으로 두번째 풀이보다 좋지 않게 나온 듯 합니다! 결국 저는 포인터를 각각 처음과 끝에 두는 방식으로 풀이를 완료했고, 현석님의 getArea를 유용하게 사용하였습니다 :p

Container With Most Water

📑 문제

✏️ 풀이