문제링크 : https://leetcode.com/problems/container-with-most-water/
문제 추상화
- 물을 담을때 가장 많이 담기는 크기 구하기
- 물이 담긴다 >> 두 막대중 더 작은것 * 두 막대의 거리
- 둘다 높아야되고, 사이가 멀어야함
아이디어
- 브루트포스 접근 : 각 막대에 대해서 모든 막대를 탐색해보자
- 시간복잡도 : O(N^2) > 1e10 > 시간초과
- 시간복잡도 줄일수 있는방법
- 이진탐색? > 정렬하고 있지 않아서 불가
- DP? > 이전 값을 재활용 할 수가 없음
- 투포인터? > 전체에서 가장 큰 값을 찾아야함
- st, en이 왼쪽에서 시작? > st, en을 움직이는 조건이 어려움
- st은 왼쪽에서, en은 오른쪽에서 시작
- 둘중에 작은 값을 움직이면 됨 > 이렇게 해보자
- 투포인터 st 왼쪽에서, en 오른쪽에서
- 최대값을 갱신해줌
- 둘중에 더 작은값이 이동
- 최대값 리턴
시간복잡도 계산
- 투포인터 순회 : O(N)
자료구조
- 막대 높이 : int[N]
- 막대 최대높이 : 1e4 > INT 가능
- 투포인터 최대값 : 1e4 * 1e5 > 1e9 > INT 가능
코드(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: int maxArea(vector<int>& height) { int st = 0; int en = height.size()-1; int maxv = 0; while(st!=en) { int area = min(height[st], height[en]) * (en-st); maxv = max(maxv, area); // 더 작은값을 움직이자 // 같을때 어떤 값을 움직이냐가 차이가 있을까? > 없을 듯 if(height[st] > height[en]) en--; else st++; } return maxv; } }; | cs |
문제유형
- Two pointer - 배열 순회
- N^2 를 N에 푸는 방법
- 어떤 연산값을 구해야할때, 순차적으로 구해야하는 경우