[알고리즘] 문제 해결 패턴 - 기본: Two Pointers

1. Two Pointers

• 배열이나 리스트 같은 선형데이터 구조에서 사용
• 두개의 포인터를 동시에 움직여 가며 해결
• 한쌍의 값이나 조건을 충족시키는 무언가를 찾는 문제
  • ex) 정렬된 배열 주어졌을때, sum라는 함수 작성 함수는 합이 0이되는 첫번째쌍을 찾아야함

대표적인 문제 예시

: LeetCode - Container With Most Water

주어진 배열에서 두 개의 세로선과 x축이 이루는 면적이 최대가 되는 값을 찾는 문제입니다. 즉, 각 세로선의 높이를 요소로 갖는 배열이 주어졌을 때, 두 개의 세로선과 x축으로 이루는 가장 큰 면적을 찾는 문제입니다.

data example 1
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

data example 2
Input: height = [1,1]
Output: 1

data example 3
Input: height = [4,3,2,1,4]
Output: 16

 

 

Bad Solution : O(n^2)

function maxAreaBad(height) {
    let maxArea = 0;
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));
        }
    }
    return maxArea;
}

 

알고리즘 적용 : O(n)

function maxArea(height) {
    let maxArea = 0;
    let left = 0;
    let right = height.length - 1;
    
    while (left < right) {
        const h = Math.min(height[left], height[right]);
        const w = right - left;
        maxArea = Math.max(maxArea, h * w);
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}