[효율성/투포인터스 알고리즘] 두 배열 합치기

문제

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

▣ 입력설명
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

▣ 출력설명
오름차순으로 정렬된 배열을 출력합니다.

▣ 입력예제 1 3
135
5

23679

▣ 출력예제 1 12335679

[자바스크립트 알고리즘 문제풀이]

두 배열 합치기

---

결과

O

내가 푼 방식

const solution = (arr1, arr2) => {
let answer = [...arr1,...arr2];
return answer.sort((a,b) => a-b);
}

 접근과정

1. spread 연산자로 두 배열을 합치고 sort로 오름차순 해준다.

 

---

모범답안

 

function solution(arr1, arr2){
    let answer=[];
    let n=arr1.length;
    let m=arr2.length;
    let p1=p2=0;
    while(p1<n && p2<m){ // 둘 다 length가 끝나지 않았을 때 
        if(arr1[p1]<=arr2[p2]) answer.push(arr1[p1++]); 
        // arr[p1]이 같거나 작다면 answer에 push하고 해당 포인터의 값을 늘려준다.
        // 후치 연산자를 통해 push 후 p1의 값을 늘려준다.
        else answer.push(arr2[p2++]);
        // 그 외 경우 arr2의 값을 push하고 포인터를 늘려준다
    }
    // 이렇게 해도 둘의 length가 다를 경우 더 큰 length를 가진 배열은 아직 값이 남아있다.
    while(p1<n) answer.push(arr1[p1++]);// 
    // p1이 아직 남아 있다면 그대로 push하고 포인터를 늘려준다.
    while(p2<m) answer.push(arr2[p2++]); 
    // p2가 아직 남아 있다면 그대로 push하고 포인터를 늘려준다.
    return answer;
}

리뷰

굉장히 쉬운 문제인 줄 알았는데 투포인터스(two pointers) 알고리즘을 쓰는 문제였다. 

sort 함수를 쓸 경우 n 개를 sort 한가면 nlogn의 시간 복잡도를 가진다고 한다. 

하지만 반복문을 쓸 경우 매개변수로 받는 두 배열의 length를 각각 n,m 이라 한다면 n + m 의 시간 복잡도를 가지므로

반복문을 쓰는게 효율적이게 된다.