[코딩테스트] 공통원소 구하기

나의 풀이

    function solution(arr1, arr2) {
            let answer = [];
            let newArr = arr1.concat(arr2);
            newArr.sort()
            console.log(newArr)
            return answer;
        }

        let a = [1, 3, 5];
        let b = [2, 3, 6, 7, 9];
        console.log(solution(a, b));

 

이렇게 풀었는데 해설에서는 sort 는 nlogn 시간복잡도를 가진다고하고 

투 포인터 알고리즘을 사용하면 n +m 시간복잡도를 가져서 푼다고한다. 

 

   function solution(arr1, arr2) {
            let answer = [];
     
            for (let j = 0; j < a.length; j++) {
                for (let k = 0; k < b.length; k++) {
                    if (a[j] > b[k]) {
                        answer.push(b[k])
                    } else if (a[j] < b[k]) {
                        answer.push(a[j])
                    }
                }
            }
            console.log(answer)
            for (let i = b.length - a.legth; i < b.length; i++) {
                answer.push(b)
            }
            return answer;
        }

        let a = [1, 3, 5];
        let b = [2, 3, 6, 7, 9];
        console.log(solution(a, b));

두번째 풀이로 위처럼 해봤지만 잘 안되었었고 판단 미스가 있었는데 

경우의 수가 다 돌고나서 나머지 경우의 수를 2가지로 나눠줘야하는데 나는 1개만 나눠줬었다.

모범 답안

   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));

풀이 핵심 포인트 1) p1=p2=0 으로 지정

2) 경우의수가 끝나고 남을경우 2개로 지정해서 따로 각각 써줘야한다는점

3) while() 안에 &&가 있으면 둘중하나가 거짓이 되면 끝난다 ( 이유는 and 연산자 이기때문 )