LeetCode : 11. Container With Most Water

생각보다 이런 유형의 문제들이 여러 기업들의 코딩테스트에 많이 출제된다.

거의 대부분 이런 문제들은 투포인터로 푸는 것이 시간복잡도를 줄일 수 있는 현명한 방법이다.

 

물론, Brute Force로 풀 수 있겠지만... O(n^2)이면 크기에 따라 Time Limit이 찍힐 수도 있다.

LeetCode의 경우 C++기준으로 Time Limit이 뜬다.

 

투포인터

시간복잡도 : O(n)

// Two-pointer
class Solution {
public:
    int maxArea(vector<int>& height) {
        // 어차피 짧은 높이에 의해 넓이가 결정되기 때문에
        // 맨끝 양쪽에서 시작해서 둘 중 짧은 것을 다음으로 넘어간다.
        int Start = 0;
        int End = height.size()-1;
        int ans = 0;
        
        while(Start<End){
            if(height[Start]<height[End]){
                if(ans<height[Start]*(End-Start)){
                    ans = height[Start]*(End-Start);
                }
                Start++;
            }else{
                if(ans<height[End]*(End-Start)){
                    ans = height[End]*(End-Start);
                }
                End--;
            }
        }
 
        return ans;
    }
};