투포인터 알고리즘(프로그래머스 Lv.2 구명보트)

투포인터 알고리즘

투포인터 알고리즘은 문자열 혹은 1차원 배열에서 서로 다른 원소를 가리키는 2개의 포인터를 사용해 문제를 해결합니다.
주요 특징은 다음과 같습니다.

• 시간복잡도가 개선됩니다. O(n^2) 👉🏻 O(n)
• 다음 2가지 경우에 사용합니다.
  • 연속된 구간의 원소를 처리하는 경우
  • 정렬된 배열에서 특정값을 구하는 경우

🍀 코드

function solution(people, limit) {
    people.sort((a, b) => b - a);
    let [left, right] = [0, people.length - 1];
    let answer = 0;
    
    while (left < right) {
        let weightSum = people[left] + people[right];
        if (weightSum > limit) {
            left++;
        } else {
            left++;
            right--;
        }
        answer++;
    }
    
    if (left === right) answer++;
    
    return answer;
}

그리디 알고리즘을 사용했습니다.
우선 people 배열에 대해 내림차순으로 정렬했습니다.
포인터 2개는 정렬된 people 배열의 양 끝으로 지정했습니다.