🟠[Leet code - 11] Container With Most Water ✅

Container With Most Water - LeetCode

문제

• Input
  정수 배열 height
• Output
  (두 원소의 인덱스 차이 * 두 원소 중 작은 값)중 최대 값

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

| O(1) : 크게 상관 없음 | O(log n) : 크게  상관 없음 | O(n) :  100'000'000 (1억) | O(n log n) : 1'000'000 (100만) | O(n^2) : 10'000 (1만) |

---

 

$2 \le n \le 100'000$으로 $n \log n$부터 고려해볼 수 있다.

 

 

해결 과정

$n^2$이 생각났지만 통과 불가능한 복잡도이기에 제외했다.

배열에서 어떤 두 가지를 고른다는 문장에서, 이전에 풀었던 투 포인터 방식의 문제가 생각나서 그쪽으로 생각을 해보았다.

 

양 끝에 인덱스를 두고 두 원소중 작은 쪽이 움직이면서 최대값을 갱신하는 방법이다.

이게 가능한 이유는 그리디와 비슷하다고 생각하는데, 작은쪽이 움직이면 적어도 답과 멀어지지는 않는 것 같기 때문이다.

이런 방법이면 $O(n)$에 풀이가 가능하다.

 

추가로 Output의 최대값은 $0 <= height[i] <= 10'000$ 으로  $100'000 * 10'000 = 1'000'000'000$이다.

그래서 int로 충분히 가능하기에 int로 설정했다.

 

아래와 같은 의사코드를 작성 후 구현하였다.

int left, right;
left = 0
right = n.size -1
int ret = INT_MIN;

WHILE (left < right)
{
    //근데 같으면?? 어느쪽이든 상관 없는거 같음
    IF (n[left] <= n[right])
        최대값 계산 & left ++;
    ELSE IF (n[left] > n[right])
        최대값 계산 & right --;
}

return ret;

 

 

구현

의사코드에서 달라진 점은, 최대 값 계산을 제일 먼저 수행하여 중복 코드를 제거했다.

그리고 ret의 초기값인데, height의 최소 값이 0이기 때문에 간단하게 -1로 설정했다.

int maxArea(vector<int>& height) 
{
    auto& h = height;
    int l = 0, r = h.size() - 1, ret = -1;

    while (l < r)
    {
        // 현재 최대값 계산
        ret = max(ret,(r - l) * min(h[l], h[r]));
        // 인덱스 이동
        (h[l] <= h[r]) ? ++l : --r;
    }

    return ret;
}

 

 

되돌아보기

투 포인터

배열에서 어떤 두 값을 고르거나 이용해야할 때 적극적으로 투 포인터를 떠올려도 괜찮겠다는 생각을 했다.

 

증명

작은쪽이 움직이면 적어도 답과 멀어지지는 않는다는 건 감으로는 알았으나,

명확하게 설명할 수 있는 근거를 생각하기 어려워서 이 부분을 좀 더 알아보았다.

 

우선 왼쪽의 값이 더 작다고 가정을 해본다. $$h[l] \le h[r]$$

 

그럼 현재 넓이는 아래와 같다.$$A = (r - l) \times h[l]$$

 

 

여기서 값이 큰 r을 이동하여 정답이 될수 없음의 증명을 시도한다.

오른쪽 포인터를 줄여 $r'$라고 한다면, 새 넓이$A'$는 아래와 같다.$$A' = (r' - l) \times min(h[l], h[r'])$$

 

여기서 이전 값과 비교하면, 가로길이는  $r' < r$이기 때문에 더 커질 수 없고,

$min(h[l], h[r']) \le h[l]$으로 min을 사용하기 때문에 세로길이 또한 이전 값보다 더 커질 수 없다.

 

 

그렇기 때문에 아래와 같이 정리가 가능하다.

$$(r' - l) \times min(h[l], h[r']) \le (r - l) \times min(h[l], h[r]) \\ = A' \le A$$

 

 

그래서 왼쪽이 더 작은 상태에서 오른쪽 포인터를 이동하면 현재보다 더 큰 넓이는 절대 만들 수 없다는 증명이 가능하며,

작은쪽을 움직여도 정답을 놓치지 않는다는 결론까지 도달이 가능해진다.