[Algorithm] 투 포인터 알고리즘 (Tow Pointer Algorithm)

1. 투 포인터 알고리즘(Tow Pointer Algorithm)이란?

투 포인터 알고리즘은 말 그대로 두 개의 포인터 위치를 기록하며 처리하는 알고리즘을 말한다.

주로 정열된 배열에서 목표 값에 해당하는 요소를 찾을때 많이 사용한다. 

 

투 포인터 알고리즘에는 서로를 향해 두 포인터를 움직이는 것과

같은 방향으로 두 포인터를  움직이는 것, 2가지 유형이 있다.

 

1) 서로를 향해 두 포인터를 움직이는 유형

 

두 개의 포인터를 시작과 끝에 설정하고, 포인터가 만날때까지 서로를 향해 이동한다. 

 

 

2) 같은 방향으로 두 포인터를 움직이는 유형

 

두 개의 포인터를 같은 위치에 설정하고, 동일한 방향으로 포인터를 이동한다. 

 

 

 

2. 예제 

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

//내코드
function solution(arr1, arr2) {
    let answer = [];

    answer = arr1.concat(arr2);
    answer.sort((a, b) => a - b);

    return answer
}
let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));

 

처음 내가 문제를 풀었던 방법이다. 투 포인트 알고리즘을 사용하지 않고 concat과 sort를 사용했다.

아마 알고리즘을 배우지않고, 처음 짜는 사람이라면 나처럼 짰을 것 같다. 

 

필자도 '합쳐', '오름차순' 이라는 글자만보고 concat, sort 메서드가 떠올라서 바로 코드를 짰는데..

시간복잡도를 생각하지 않고 짰던게 실수였다.

 

후에 생각해보니 위 풀이의 시간복잡도는 O(nlogn)이였다.

concat이 O(n), sort가 O(nlogn)이기 때문이다.

 

위 문제는 투 포인터 알고리즘을 사용하면 O(n)으로 줄일 수 있다. 

 

 

//강의코드
function solution(arr1, arr2) {
    let answer = [];
    let p1 = p2 = 0;  //포인트를 값 자체에 두는게 아니라 idx에 

    let n = arr1.length;
    let m = arr2.length;

    //p1, 혹은 p2가 끝나면 끝
    while (p1 < n && p2 < m) {
        if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
        //p1의 값을 넣은 후 해당 값을 +1해줌
        //다음 렌더링부터 p1의 값이 증가함
        else answer.push(arr2[p2++]);
    }

    //p1이 만약 나중에 끝났다면 아직 p1의 값이 n보다 작음
    //p1이 끝나지 않았다면, 해당 값이 끝날때까지 돌면서 값을 넣어줌 
    while (p1 < n) answer.push(arr1[p1++]);
    while (p2 < m) answer.push(arr2[p2++]);

    return answer
}
let a = [1, 3, 5];
let b = [2, 3, 6, 7, 9];
console.log(solution(a, b));

 

투 포인터 알고리즘을 사용한 풀이방법이다.

각각의 배열 인텍스에 포인터를 주고, 앞으로 이동하면서 정렬하는 방법이다. 

 

 

 

첫 번째 arr의 0번째 인덱스와 두 번째 arr의 0번째 인덱스에 포인터를 준다.

그리고 두 값을 비교하여 더 작은 숫자를 넣어주고, 포인터를 한 칸 이동해준다.

 

이를 배열의 길이만큼 반복해서 오름차순으로 정렬하면 된다. 

이제 코드를 하나하나 살펴보자. 

 

① 변수 선언

let answer = [];
let p1 = p2 = 0;  //포인트를 값 자체에 두는게 아니라 idx에 

let n = arr1.length;
let m = arr2.length;

 

처음엔 변수를 선언해 준다. 

answer은 정답을 담을 배열이고, p1과 p2는 각각의 인덱스를 담을 포인터이다. 

 

그리고 각 배열의 length를 변수로 설정해준다.

(좀 더 편하게 사용하려고)

 

 

② 반복문 

//p1, 혹은 p2가 끝나면 끝
while (p1 < n && p2 < m) {
    if (arr1[p1] <= arr2[p2]) answer.push(arr1[p1++]);
    //p1의 값을 넣은 후 해당 값을 +1해줌
    //다음 렌더링부터 p1의 값이 증가함
    else answer.push(arr2[p2++]);
}

 

p1 혹은 p2의 값이 각 길이(n, m)보다 작을때까지 while(반복)을 실행한다.

 

 

그 후 arr1[p1]의 값이 arr2[p2] 보다 작으면, 해당 값을 answer에 넣어주고 포인터를 ++해준다.

그럼 answer엔 1이 들어가고 arr1이 한 칸 앞으로 가게된다.

 

 

만일 이 반대라면 arr2[p2]의 값을 넣어주고 포인터를 ++해준다. 

그럼 answer에는 2가 들어가고, arr2가 한 칸 앞으로 가게된다.

 

이를 반복하다보면 answer엔 1, 2, 3, 3, 5가 들어가고 해당 반복문은 끝이난다.

(p1의 값이 arr1.length보다 작지않으므로 = arr1의 배열이 다 들어갔으므로)

 

 

③ 나머지 배열 넣기 

//p1이 만약 나중에 끝났다면 아직 p1의 값이 n보다 작음
//p1이 끝나지 않았다면, 해당 값이 끝날때까지 돌면서 값을 넣어줌 
while (p1 < n) answer.push(arr1[p1++]);
while (p2 < m) answer.push(arr2[p2++]);

 

그럼 마지막으로 p1, p2의 배열이 끝났는지 확인해주고, 끝나지 않았다면 위와 같이 반복문을 돌려준다.