LeetCode 11번 문제를 Two Pointers 패턴으로 O(n²) 브루트포스에서 O(n) 단일 패스 알고리즘으로 최적화

Context

배열의 두 요소를 선택해 최대 면적을 구하는 문제는 처음 보면 기하학 문제로 보인다. 브루트포스 접근은 모든 쌍을 검사하므로 O(n²) 시간복잡도로 n=100,000일 때 100억 번의 연산이 필요해 Time Limit Exceeded 판정을 받는다.

Technical Solution

• 양 끝점에서 시작: 배열의 가장 왼쪽(index 0)과 가장 오른쪽(index n-1)에 포인터를 배치해 최대 너비를 확보
• 짧은 선을 이동: 더 안쪽으로 이동하면 너비는 항상 감소하므로, 높이가 증가할 가능성이 있는 쪽만 이동
• 핵심 원리: 현재 면적이 짧은 선의 높이로 제한되므로, 긴 선의 포인터를 이동해도 면적이 증가할 수 없음
• 단일 패스 순회: 두 포인터가 만날 때까지 한 번만 배열을 순회하므로 O(n) 시간복잡도 달성
• 공간복잡도 O(1): 추가 자료구조 없이 포인터 두 개만 사용

Impact

• 시간복잡도: O(n²) → O(n) (n=100,000일 때 100억 → 100만 연산)
• 공간복잡도: O(1) 유지
• LeetCode 판정: Time Limit Exceeded → 통과

Key Takeaway

최적화 알고리즘의 핵심은 코드 단순성이 아니라 문제의 제약조건을 정확히 파악하는 직관이다. 이 경우 "더 짧은 선이 면적의 상한선"이라는 관찰이 Two Pointers 전략을 정당화하므로, 엔지니어는 문제의 수학적 성질을 먼저 이해한 후 알고리즘을 설계해야 한다.