[C] LeetCode 11. Container With Most Water

 

문제

번역

높이 n을 갖는 정수 배열 height가 주어졌다. n개의 수직선이 그려져 있고, i번째 선은 (i, 0) 부터 (i, height[i]) 까지 그려져 있다.

이 수직선들 중 2개를 골라서 x축과 함께 하나의 컨테이너를 만들때 가장 많은 물을 담을 수 있는 경우의 수를 구하여라.

단 컨테이너를 기울일 수는 없다.

 

접근 방법 및 소스 코드

그림을 보고 직관적으로 생각했다.

양 끝 점에서 시작해서 막대를 움직여가며 가장 많은 물을 담을 수 있을 때의 물을 저장하면 될 것 같았다.

 

이를 위해 투포인터 기법을 사용했다.

초기에 i = 0 , j = n-1로 세팅하고 \(min(height[i], height[j]) * (j-i)\) 로 현재 컨테이너의 용량을 재고 매번 갱신했다.

그리고 포인터를 움직일때는 더 낮은 쪽을 움직이게 했다. 그래야지 더 큰 값을 찾아볼 수 있을테니. 

 

int min(int a, int b) { return (a < b) ? a : b ;}

int maxArea(int* height, int heightSize) {
    int i = 0, j = heightSize -1, maxi = -1;
    while(i<j) {
        int mini = min(height[i], height[j]) * (j - i);
        maxi = (maxi < mini) ? mini : maxi;
        if(height[i] < height[j]) i++;
        else j--;
    } 
    return maxi;
}

 

메모리를 많이 쓰긴 해도 한방에 풀었다 히히..!