[투포인터] 두 배열 합치기

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

오름차순으로 정렬이 된 두 배열이 주어지면 이 배열들을 오름차순으로 합쳐 출력한다.

 

 

👉 입력

첫 번째 줄에 첫 번째 배열의 크기 N이 주어진다.

두 번째 줄에 N개의 배열 원소가 주어진다.

세 번째 줄에 두 번째 배열의 크기 M이 주어진다.

네 번째 줄에 M개의 배열 원소가 주어진다.

 

이때 주어진 배열의 원소들은 오름차순으로 정렬되어 있으며 N과 M은 1 이상 100 이하의 값을 가진다.

 

 

👈 출력

오름차순으로 정렬된 배열을 출력한다.

 

 

💡 사용된 개념

투 포인터 알고리즘(Two Pointers)

리스트에 순차적으로 접근해야 할 때 2개의 pointer의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

 

투 포인터 알고리즘의 예시로 특정한 합을 가지는 부분 연속 수열 찾기 문제가 있다.

 

* 특정한 합을 가지는 부분 연속 수열 찾기

자연수로 구성된 리스트가 주어질 때, 부분 연속 수열의 합이 특정값을 가지는 횟수를 카운트하는 문제이다.

이 문제에서 부분 연속 수열의 시작점을 start, 끝점을 end, 특정 부분합을 M이라고 할 때 구체적인 알고리즘은 다음과 같다.

 

1. start와 end가 주어진 리스트의 첫 번째 원소(인덱스 0)를 가리킨다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작으면 end를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같으면 start를 증가시킨다.
5. 모든 경우를 확인할 때까지 2 ~ 4의 과정을 반복한다.

 

이 문제에서는 start와 end의 위치를 기록해 부분합을 M과 비교하고 있다.

이러한 방식의 알고리즘이 투 포인터 알고리즘이다.

 

 

📝 풀이

 

function solution(arr1, arr2) {
    let answer = [];
    let n = arr1.length;
    let m = arr2.length;
    let p1 = p2 = 0; // 각 배열의 요소를 가리킬 포인터

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

 

오름차순으로 정렬된 배열인 arr1과 arr2가 입력으로 들어왔다.

arr1의 위치를 기록할 변수를 p1, arr2의 위치를 기록할 변수를 p2라고 선언한 뒤 0으로 초기화한다.

 

while문을 돌며 현재 p1, p2가 가리키는 두 배열의 원소를 비교한다.

이때 둘 중 작은 값을 answer에 넣고 해당 배열의 포인터 값을 증가시킨다.

 

이렇게 되면 첫 번째 while문이 끝나는 조건은 arr1과 arr2 둘 중 하나의 순회가 끝났을 때이다.

따라서 아직 순회할 원소가 남은 배열은 남은 원소가 모두 이미 순회를 마친 배열의 원소들보다 크다는 뜻이므로 배열의 끝까지 while문을 돌며 남은 원소들을 answer에 삽입한다.

 

 

 

그림으로 설명하면 다음과 같다.

빨간색 화살표는 p1, 파란색 화살표는 p2이다.

 

• p1, p2가 주어진 리스트의 첫 번째 원소를 가리킨다.

 

• 1과 2를 비교했을 때 1이 2보다 작기 때문에 answer에는 1이 추가되고 p1이 arr1의 다음 원소를 가리킨다.

 

• 3과 2를 비교했을 때 2가 더 작기 때문에 answer에는 2가 추가되고 p2가 arr2의 다음 원소를 가리킨다.

 

• 3과 3을 비교했을 때 arr1의 원소(3)가 arr2의 원소(3)보다 작지 않기 때문에 else문에 걸려 arr2의 3이 answer에 추가되고 p2가 arr2의 다음 원소를 가리킨다.

 

• 위의 과정을 반복하다 p1이 arr1의 길이를 초과했다면 첫 번째 while문이 끝난다. 이때 arr2의 남은 원소들은 모두 arr1의 원소보다 크다.

 

• p2를 arr2의 길이만큼 증가시키며 arr2의 나머지 원소들을 answer에 추가한다.

 

이렇게 answer에는 arr1과 arr2의 원소를 오름차순으로 합친 것이 저장된다.