[코딩테스트] 투 포인터 알고리즘

투 포인터 알고리즘 (Two Pointer Algorithm)

• 두 개의 포인터(인덱스)를 이용해서 리스트를 순회하는 알고리즘 기법
• 대부분 정렬된 배열을 기반으로 한다.
• 두 포인터가 같은 방향으로 이동하거나, 양쪽 끝에서 가운데로 이동하면서 문제를 해결한다.
• 시간복잡도를 O(N^2)에서 O(n) 또는 O(n log n)까지 줄일 수 있다.

언제 사용하는가?

상황	설명
정렬된 배열에서 합이 특정 값이 되는 쌍 찾기	예: 두 수의 합, 삼총사, 투썸
연속된 구간(슬라이딩 윈도우)의 최댓값/최소값/조건 만족 여부 찾기	예: 부분합, 최대 길이 구간, 중복 없는 부분 문자열
두 배열 또는 문자열을 동시에 순회하면서 비교	예: 두 리스트 병합, 부분 문자열 비교, 투 리스트 정렬 비교

예시 문제 : 프로그래머스 구명보트

문제 바로 가기

해결 과정

1. 전략 개요 구명보트 수를 최소화하려면 가장 무거운 사람부터 가능한 한 가벼운 사람과 함께 태우는 것이 최적이다.

2. 정렬 및 포인터 설정

   • people 배열을 오름차순으로 정렬한다.
   • 두 개의 포인터를 사용합니다:
     • left: 가장 가벼운 사람 (배열의 앞쪽)
     • right: 가장 무거운 사람 (배열의 뒤쪽)

3. 탑승 조건 확인

   • people[left] + people[right] <= limit
     → 두 사람이 함께 탈 수 있으므로 둘 다 태움
     → left++, right--
   • 아니라면
     → 무거운 사람 혼자 탑승
     → right--만 이동

4. 탐색 종료 조건 left > right가 되면 탐색 종료

   • left === right : 한 사람만 남은 경우 혼자 탑승하고 탐색 종료

코드

function solution(people, limit) {
    let lt = 0;
    let rt = people.length - 1;
    let cnt = 0;
    people.sort((a, b) => a-b);
    
    while(lt <= rt) {
        if(lt === rt){
            cnt++;
            break;
        }
        
        if(people[lt] + people[rt] <= limit) {
            cnt++;
            lt++;
            rt--;
           
        } else {
            cnt++;
            rt--;
        }
    }
    
    return cnt;
}