[Algorithm] 두 배열 합치기(Two Pointers)

❐ 두 배열 합치기

▶︎ 문제

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

 

▷ 입력 예제

[1, 3, 5], [2, 3, 6, 7, 9]

 

▶︎ 출력 예제

[1, 2, 3, 3, 5, 6, 7, 9]

 

▷ 문제설명

시간복잡도나 효율성을 고려하지 않고 문제를 풀 수 있는 가장 간단한 방법을 생각해보자. 두 개의 배열을 하나로 합친 뒤 자바스크립트의 sort( ) 메서드를 활용해서 배열을 정렬하는 방법을 떠올릴 수 있다. 이 방법은 간단하지만 최선이라고는 할 수 없다.

 

자바스크립트에서 사용되는 v8 엔진은 'Tim Sort'의 정렬 알고리즘을 사용하는데, 이것은 Merge Sort를 기반으로 최적화한 알고리즘이고 O(n log n)의 시간복잡도를 가진다. 

(Tim Sort 더 알아보기 https://d2.naver.com/helloworld/0315536)

 

sort( ) 메서드 보다 빠르게 답을 구할 수 있는 방법은 없을까? 투포인터(Two Pointers) 알고리즘을 통해 O(n)의 시간복잡도로 문제를 해결할 수 있다. 투포인터 알고리즘은 일차원 배열에서 각자 다른 원소를 가리키는 있는 2개의 포인터를 조작해서 값을 탐색하는 방법이다. 

 

 

O(n)과 O(nlog n)의 차이는 작은 수의 연산에서는 잘 느껴지지 않을 수 있지만 탐색하려는 경우의 수가 많아질수록 효율성의 측면에서 더 큰 격차로 벌어질 것이다. 

 

문제를 투포인터 알고리즘으로 해결하는 과정은 다음과 같다.

먼저 두 개의 포인터 p1과 p2이 배열의 첫번째 인덱스를 가리키도록 한다. 

각각의 포인터가 가리키는 값을 비교한다. p1은 숫자 1을, p2는 숫자 2를 가리킨다. 둘을 비교했을 때 p1이 가리키는 값이 더 작으므로 정답 배열에 숫자 1을 push한 후 p1을 다음 인덱스로 옮긴다. 

 

이제 p1이 가리키는 인덱스는 숫자 3의 값을 가지고, p2는 2의 값을 가진다. p2의 값이 더 작으므로 정답 배열에 숫자 2를 push한 후 p2를 다음 인덱스로 옮긴다. 

이제 p1과 p2가 가리키는 인덱스의 값이 동일하다. p1과 p2 둘 중 어떤 포인터를 옮겨도 상관없다. p2를 옮겨보자.

앞선 단계와 동일하게 진행한다. 

앞선 단계와 동일하게 진행한다. 이제 p1 포인터는 배열의 마지막 인덱스를 가리킨다. 마지막 인덱스까지 탐색을 완료한 후에는 나머지 배열의 탐색만 완료한다. 

 

 

▶︎ 내 답안

function solution(arr1, arr2) {
    let answer = [];
    let p1 = (p2 = 0);
    let n = arr1.length;
    let m = arr2.length;

    while (p1 < n && p2 < m) {
        if (arr1[p1] >= arr2[p2]) {
            answer.push(arr2[p2++]);
        } else {
            answer.push(arr1[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));

 

let p1 = (p2 = 0);

먼저 p1, p2 두 개의 포인터를 0으로 초기화한다.p1 포인터는 arr1을, p2 포인터는 arr2를 인덱스 0부터 가리키게 될 것이다. 

 

while (p1 < n && p2 < m) {
	...
}

변수 n과 m은 각각 arr1과 arr2 배열의 길이를 담고 있다. 

p1과 p2 포인터 중 하나라도 마지막 인덱스를 벗어나면 while문을 종료하도록 조건을 설정해 놓는다. 

 

if (arr1[p1] >= arr2[p2]) {
    answer.push(arr2[p2++]);
} else {
    answer.push(arr1[p1++]);
}

만약 p1 포인터가 가리키는 값이 p2 포인터가 가리키는 값보다 크거나 같다면 p2 포인터가 가리키는 값을 answer 배열에 추가하고 p2 포인터를 다음 인덱스로 이동시킨다. 둘 중 더 작은 값을 answer에 push하는 이유는 문제의 조건이 오름차순으로 배열을 정렬하는 것이기 때문이다. 

 

p1과 p2 포인터 둘 중 하나가 마지막 인덱스를 벗어나면 앞서 언급했던 while문은 종료될 것이다. 하나의 포인터가 탐색을 마쳤더라도 다른 하나의 포인터는 탐색을 마치지 못한 상황이 발생할 수 있다. while문 활용하여 남아있는 포인터의 탐색을 완료하기 위한 코드를 작성한다. 

while (p1 < n) answer.push(arr1[p1++]);
while (p2 < m) answer.push(arr2[p2++]);

 

남아있는 포인터의 탐색까지 완료하고 나면 완성된 answer 배열을 return 하면서 함수는 완료된다.