릿코드 11번 문제 Container With Most Water 자바스크립트 문제 해석 및 풀이 Leetcode 11 Javascript

오늘은 릿코드 11번 문제인 Container With Most Water 자바스크립트 문제 풀이입니다.

릿코드 11번 문제

문제설명

이 문제 같은 경우에는 먼저 설명드리자면 1차원 배열이 주어졌을 때에 그 배열로 그래프를 만들었을 때 컨테이너에 물이 가장 많이 담기는 원소 2개를 구하는 문제입니다. 릿코드에 예시 사진을 살펴보겠습니다.

Most Water in the possible containers

위 예제에서 보면 height으로 들어온 배열로 그래프를 만들었죠? 해당 그래프에서 임의로 두 개의 값을 선택했을 때, 그 두개의 값을 벽으로 보고 물을 채워 넣었을 때의 최댓값을 구하는 겁니다. 예제에서는 7*7 = 49가 되어 49가 Output이 되겠습니다.

릿코드 문제 전체 내용은 다들 아셔서 방문하셨을 거라 생각하지만 혹시 모르니 맨 아래에 넣어두겠습니다. 필요하신 분은 밑에서 문제를 먼저 보시고 다시 올라오셔서 포스팅을 읽어주세요.

 

이 문제의 경우, brute-force로 접근해서 모든 경우의 수를 다 구하여 값을 계산할 경우 O(n^2) 이 되어 'Time Limit Exceded'가 됩니다. 올바른 접근 방법으로는 Two Pointer를 쓰는 방법이 있습니다.

 

문제풀이

Two-Pointer 이용

l(left)과 r(right) 두 개의 포인터를 이용해서 max값을 계속 갱신해 나가는 방법을 생각해 볼 수 있습니다.

코드부터 살펴보겠습니다.

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let max = 0;
    let l = 0; // first element
    let r = height.length-1; // last element
    while (l < r) {
        max = Math.max(max, (r - l) * Math.min(height[l], height[r]));
        if (height[l] < height[r]) l++;
        else r--;
    }
    return max;
};

우선 리턴될 값인 max에는 0을 넣어둡니다.

l은 왼쪽부터, r은 오른쪽부터 시작해서 점점 중간으로 좁혀가겠습니다.

while 루프를 이용해서 l과 r 두 포인터가 교차될 때까지 두 값중 큰 값을 유지하고 작은 값 포인터를 이동해줍니다.

max값에는 루프 안에서 이동된 r, l 포인터를 이용해 현재 값과 해당 루프에서 계산된 물의 부피 중 큰 것이 다시 대입됩니다.

루프를 다 돌면 max를 리턴해 주면 됩니다.

 

Two-Pointer 성능

Container with Most Water solved with Two-Pointer

1. 시간복잡도는 인자로 들어온 height 배열의 갯수만큼 루프가 돌았으니 O(n)이 됩니다.
2. 공간복잡도는 별도의 공간을 생성해주지 않았기 때문에 O(1)이 됩니다.

---

이상으로 릿코드 11번 문제 Container with most water을 풀어보았습니다.

 

아래는 전체 문제 내용입니다.

 

11. Container With Most Water

 

 

 

Medium

 

 

22.4K

 

1.2K

 

 

Companies

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

 

※ 앞으로 모든 문제를 JavaScript 로 올릴 예정입니다.

릿코드 연습을 하며 올린 포스팅이므로 간혹 틀린 부분이 있을 수 있습니다.

혹시 잘못된 부분이 있을 경우 댓글 남겨주시면 감사드리겠습니다.

다른 문제 풀이도 깃헙에서 확인 할 수 있습니다.