2022/01/25) 1. 두 배열 합치기 [효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)]

1. 문제

<두 배열 합치기>
: 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성한다.

2. 해결 방법

1. 문제에서 "오름차순"으로 정렬이 된 두 배열이 주어진다고 한다. 그러므로 투포인터를 할 수 있다! 정리하자면, 입력으로 주어지는 두 배열이 정렬돼 있을 경우엔 "투포인터"할 수 있다.
2. 배열의 인덱스인 p1과 p2(두 개의 포인터들)을 0으로 초기화한다.
3. 두 배열의 값을 비교하여, 값이 더 작은 걸 arr에 push하고 포인터도 이동시킨다.
4. 그러나 만약 하나의 배열이 끝이날 경우(p1<n && p2<m)엔, 남은 하나의 배열의 값들을 한 번에 다 push해줘야 한다.

3. 정답

    <script>
        function solution(arr1, arr2){
            let answer = [];
            let n = arr1.length;
            let m = arr2.length;
            let p1=p2=0; //포인터 2개 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));
    </script>

4. 내 코드와 비교

나는 concat으로 두 배열을 합친 후, sort를 이용해서 정렬했다. 그런데 이 문제는 투포인터로 풀어야 하는 거 같다.

        <script>
            function solution(arr1, arr2){
                let tmp = arr1.concat(arr2);
                tmp = tmp.sort((a,b) => (a-b));
                return tmp;
            }
            let a=[1, 3, 5];
            let b=[2, 3, 6, 7, 9];
            console.log(solution(a, b));
        </script>