[LeetCode] 11 - Container With Most Water

문제

• 링크: https://leetcode.com/problems/container-with-most-water
• 난이도: Medium
• 태그: 배열, 투 포인터, 그리디
• 결과: Time: 0 ms (100.00%), Space: 63.05 MB (10.47%)

풀이

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0;
        int r = height.size() - 1;

        int area = 0;

        while (l < r)
        {
            area = max(area, (r - l) * min(height[r], height[l]));

            if (height[l] < height[r])
            {
                l++;
            }
            else
            {
                r--;
            }
        }

        return area;
    }
};

왠지 딱 봐도 투 포인터 같은데, 완전히 해결하는데는 시간이 좀 걸렸다.

너비를 구해서 최댓값을 업데이트 해나가되, 커서의 이동을 신경써야 한다. 투 포인터로 고른 두 막대(vertical line) 중에서 짧은 쪽의 커서를 이동해야 한다. 커서를 안쪽으로 옮기면 너비를 결정짓는 factor 중 하나인 폭이 감소하기 때문에, 높이가 높은 막대는 유지시키는게 반드시 이득이기 때문이다.

배운 점과 후기

투 포인터를 판단하는 감은 OK인데, 그 틀 안에서 어떤 논리를 간파해야하는지 알아내는게 약한 것 같다. 그냥 단순히 논리력의 문제로 납작하게 뭉개고 넘기기 보다는, 어떤 것에 약한지 더 다양한 문제를 풀어봐야할 것 같다.

이 포스트는 달레 스터디(6주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.