5-1) 두 배열 합치기

김예지·2021년 9월 2일

[알고리즘] javascript 인프런 강의

목록 보기

36/91

5장은 효율성에 관련된 챕터이다. 투 포인터 알고리즘, 슬라이딩윈도우, 해쉬를 통해 효율성을 극대화한다.

문제

오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램 을 작성하세요.
[입력설명]
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다. 두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다. 네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
[출력설명]
오름차순으로 정렬된 배열을 출력합니다.

입력예제 1

3
135
5
23679

출력예제 1

1 2 3 3 5 6 7 9

문제 풀이

예습 이론

투포인터 알고리즘은 포인터 변수가 2개인 알고리즘을 뜻한다.
시간복잡도를 비교했을 때, sort()는 n개를 정렬하는데 O(nlogn), 투포인터 알고리즘은 n+m개, 즉 O(n+m)이다. 투포인터 알고리즘이 시간복잡도가 더 낮다.

코드

이 문제는 투포인터 알고리즘을 활용해서 풀 수 있다.

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(arr1, arr2){
                let answer=[];
                let n=arr1.length;
                let m=arr2.length;
                let p1=p2=0; //포인터 초기화(인덱스 0번 가리킴)
                while(p1<n && p2<m){
                    if(arr1[p1]<arr2[p2]) answer.push(arr1[p1++]); //push 후 p1+1(후위연산자!)
                    else answer.push(arr2[p2++]);
                }
                //p2는 끝나고, p1이 남았을 때
                while(p1<n) answer.push(arr1[p1++]); 
                //p1는 끝나고, p2가 남았을 때
                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));
        </script>
    </body>
</html>