[C/LeetCode] Container With Most Water

Daily LeetCoding Challenge April, Day 5

 

문제

높이가 배열로 주어졌을 때, 만들 수 있는 가장 넓은 사각형 영역의 크기 구하기 (width = 1로 고정)

 

아이디어: brute force

이중 배열을 돌면서 두개의 index를 선택하고 이를 통해 만들 수 있는 사각형의 크기와 max 값을 비교함

 

완성: time limit exceeded

눈물이 나게도 시간초과가 발생했다.

 

int min(int a, int b)
{
    return a < b ? a : b;
}
int maxArea(int* height, int heightSize){
    int max = 0;
    int temp;
    
    for(int i = 0;i<heightSize;i++)
    {
        for(int j = i + 1;j<heightSize;j++)
        {
            temp = (j - i) * min(height[i], height[j]);
            if (temp > max)
                max = temp;
        }
    }
    return max;
}

 

근데 당연함. 이런 문제는 아무래도 모든 경우의 수를 다 확인하는 것은 시간 초과의 가능성이 큼

 

 

아이디어2: Greedy

높이는 무엇에 의해 결정되는가? 바로 작은 값에 의해 결정된다.

따라서 양쪽에서 시작하여 둘 중 작은 높이에 해당하는 index를 이동시키며 넓이를 다시 계산해서 비교하면 효율적으로 찾을 수 있다.

 

완성

submission: 133ms / 11.6MB

int min(int a, int b)
{
    return a < b ? a : b;
}
int maxArea(int* height, int heightSize){
    int max = 0;
    int start = 0;
    int end = heightSize - 1;
    int temp;
    
    while (start < end)
    {
        temp = (end - start) * min(height[end], height[start]);
        if (temp > max)
            max = temp;
        if (height[end] > height[start])
            start++;
        else
            end--;
    }

    return max;
}

 

 

PLUS: Brute Force vs Greedy

brute force는 모든 경우의 수를 확인함으로써 최적의 해를 보장할 수 있다면, greedy는 현재 가장 좋아보이는 선택지를 계속 선택하는 최적화 문제 알고리즘이다. 따라서 항상 최적의 해답이 나옴을 보장할 수 없다.