[투포인터 알고리즘] 두 배열 합치기

오름차순으로 정렬이 된 두 배열을 합쳐 오름차순으로 출력

입력 예제

N(1<=N<=100)개의 배열 원소가 오름차순으로 주어집니다.

M(1<=M<=100)개의 배열 원소가 오름차순으로 주어집니다.

각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

function solution(p1,p2) {

    let result = [];
    let n = p1.length;
    let m = p2.length;
  
    // a와 b를 증가시키며 배열을 동시에 돈다.
    let a = b = 0;
  
    // a와 b가 배열의 길이보다 크면 종료
    while(a < n && b < m) {
      
      	// 두 배열의 요소 중 작은 것을 result 배열에 push
        if(p1[a] <= p2[b]) result.push(p1[a++]);
        else result.push(p2[b++]); 
    }
  
    // p1의 배열 길이가 더 긴 경우, 비교하지 않은 남은 숫자를 배열에 push
    while(a<n) result.push(p1[a++]);
  
    // 	p2의 배열 길이가 더 긴 경우, 비교하지 않은 남은 숫자를 배열에 push
    while(b<m) result.push(p2[b++]);
  
    return result;
}

let arr1 = [1,3,5];
let arr2 = [2,3,6,7,9];

console.log(solution(arr1,arr2)); // [1,2,3,3,4,5,6,7,9]

• 2중 for문을 쓰지 않고 변수 a,b를 선언해 두 배열을 동시에 돈다.

• 두 배열의 0(a,b)번째 요소를 비교하여 더 작은 수를 가진 배열의 0번째 요소를 result 배열에 넣고, 변수(a)를 증가시킨다.

• 마찬가지로 배열의 1(a)번째 요소와 다른 배열의 0(b)번째 요소를 비교하여 더 작은 수를 가진 배열의 요소를 result 배열에 넣고, 변수를 증가시켜 계속 비교

• 두 배열 중 배열의 길이가 짧은 배열까지 돌고, 남은 숫자가 있는 배열을 마저 result 배열에 넣어주면 오름차순 정렬이 자동으로 된다. ( 처음 배열이 오름차순 정렬이 되어있었기 때문 )

arr1의 1과 arr2의 2를 비교   →   result [1]
arr1의 3과 arr2의 2를 비교   →   result [1,2]
arr1의 3과 arr2의 3을 비교   →   result [1,2,3]
arr1의 5와 arr2의 3을 비교   →   result [1,2,3,3]
arr1의 5와 arr2의 6을 비교   →   result [1,2,3,3,5]
arr1의 배열이 끝나고 arr2의 남은 숫자 6,7,9를 push   →   result [1,2,3,3,5,6,7,9]