[ LeetCode _ 11 ] Container With Most Water ( by using JavaScript )

Problem

How to Solve ?

 

1.  2중 포문 || 완전 탐색

 

이 문제도 다른 문제들과 같이 완전 탐색을 해버리면 크게 어렵지는 않을 것 같았는데, 시간복잡도가 O(n^2) 로 갈 수 밖에 없어서 채택 X

 

2.  For * 2

 

투포인터를 바탕으로 문제를 풀던 도중, 포인터를 이동 시키는 기준에 대한 정답이 안나와서 1중 포문을 2번 푸는 방식으로 접근해보았다.

 

내가 생각한 접근법은

 

1) 앞 포인터만 움직여서 얻을 수 있는 최선의 자리를 찾는다.

 

2) 1번에서 찾은 앞포인터는 고정시키고, 뒤의 포인터만 이동시킨다.

 

였는데, 특정 문제가 안풀리는 오류를 가지고 있었다.

 

var maxArea = function(height) {
    let max = 0;
    let tmpIndex = 0;
    
    for ( let i = 0; i < height.length - 1; i++ ) {
        let left = i;
        let right = height.length -1;
        let container = (right-left) * Math.min(height[right], height[left]);
        
        if ( max < container ) {
            max = container;
            tmpIndex = i;
        }
        
    }
    
    for ( let j = height.length-1; j > tmpIndex; j-- ) {
        let left = tmpIndex
        let right = j;
        let container = (right-tmpIndex)  * Math.min(height[right], height[tmpIndex]);
        
        if ( max < container ) {
            max = container
        }
    }
    
    return max;
};

18 - 17 => 17 

3. 투포인터

 

다시 투포인터로 돌아와서, "어떤 기준으로 포인터를 옮길 수 있을까?" 생각해보면 좌, 우 포인터간의 크기를 비교하면서 접근 하면 해결이 된다는 것을 배울 수 있었다.

 

아무리 한 쪽 포인터의 높이가 높더라도, 반대 쪽의 포인터 길이가 짧으면 낮은 값으로 계산이 되기 때문에 더 작은 값을 포인터가 이동하는 방법으로 구현 하였다.

var maxArea = function(height) {
  let max = 0;
  let container = 0;
  let left = 0;
  let right = height.length - 1;

  while (left < right) {
      
    container = (right-left) * Math.min(height[left], height[right]);
    max = Math.max(max, container);
      
    if (height[left] < height[right]) {
      left++;
    } 
     
    else {
      right--;
    }
      
  }
  return max;
};

 

Result

Time  Submitted Status Runtime Memory Language

05/15/2021 21:38	Accepted	100 ms	48 MB	javascript
05/15/2021 21:37	Accepted	88 ms	48 MB	javascript

Container 변수를 선언여부에 따른 차이.