[Leetcode]Container With Most Water

문제) 인자인 height는 숫자로 이루어진 배열입니다. 그래프로 생각한다면 y축의 값이고, 높이 값을 갖고 있습니다.

아래의 그래프라면 height 배열은 [1, 8, 6, 2, 5, 4, 8, 3, 7] 입니다.

저 그래프에 물을 담는다고 생각하고, 물을 담을 수 있는 가장 넓은 면적의 값을 반환해주세요.

내가 생각한 로직

1. 최대 너비값(return할 값)을 변수 max로 둔다.
2. 두 막대의 index값을 lt, rt로 둔다. (lt = left, rt = right)
3. 이중 포문 내에서 height와 width를 설정해준다. (각각의 경우에서 너비값을 구한 후 max와 대조해주기 위해)
   height는 height[lt]와 height[rt] 중 더 작은 값으로 계산된다.
   width는 rt에서 lt를 뺀 값이다.
4. h와 w를 곱한 값과 max를 비교한 후, max보다 크다면 max에 해당 값을 할당해준다.
5. 최종으로 구해진 max값을 return해준다.

코드는 아래와 같다.

function getMaxArea(height) {
let max = 0;
  
  for(let lt = 0; lt <height.length-1; lt++){
    for(let rt = lt +1; rt<height.length; rt++){
  let h = Math.min(height[lt], height[rt]);
  let w = rt - lt;

      if(max <h*w) max = h*w;    
    }
  }
  return max 
  
}

이중 포문말고 다른방식도 있을까해서 while로도 풀어봤다.

function getMaxArea(height) {
 let lt = 0;
   let rt = height.length -1;
   let max = 0

  while(lt < rt){
    let h = Math.min(height[lt], height[rt]);

    let w = rt - lt;

    if(max < h*w) max = h*w;
   else lt++
   
  } 
  while(lt < rt){
    let h = Math.min(height[lt], height[rt]);

    let w = rt - lt;

    if(max < h*w) max = h*w;
   else rt--
   
  } 
   }
   return max}

1. 가장 맨 앞에 있는 index를 lt, 가장 오른쪽(끝)에 있는 index를 rt로 둔다.
2. lt가 rt보다 왼쪽에 있는 경우동안 while문을 돈다. h와 w를 구해주는 방식은 위와 동일, max보다 해당 너비가 더 크다면 max에 해당 너비값 할당해준다.
3. 만약 그렇지 않다면, lt를 오른쪽으로 한칸씩 이동해주며 값을 대조해본후 최종 max값을 구한다.
4. rt의 경우도 왼쪽으로 한칸씩 이동해주며 값 대조 후, 최종 max값 return 해준다.

위의 풀이 방식으로 정답이 나오긴 했지만, 생각해보니 lt와 rt가 중간에 있을 때의 경우의 수를 고려하지 못한 방식이라 한계가 있다.

아무래도 이중포문으로 푼 방식이 정답률 100%로,, 그냥 이중포문 쓰는걸루 ^^

추가)

위의 while두개로 푼 풀이방식의 단점을 보완해주는 아래의 풀이

출처 : 용현님 블로그에서,, 넘 좋은 방식이라 지나칠 수가 없었어요(??)

 function(height) {
    let result = 0;
    let i = 0;
    let j = height.length-1 // #1
    while(i < j){ // #2
        result = Math.max(result, Math.min(height[i], height[j])*(j-i)) // #3
        height[i] < height[j] ? i++ : j-- // #4
    } 
    return result // #5
};

🍯 마무리

사실... 거의 다 써놓고 다 날라가서 두번째 씀요^^ ㅎㅎ 다들 임시저장 계속 미리 해두시길,, ㅎㅎㅎㅎㅎ