2022/01/25) 2. 공통원소구하기 [효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)]

1. 문제

<공통원소 구하기>
: A,B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 프로그램을 작성한다.

2. 해결방법

1. 투포인터로 하기 위해, sort를 이용해 오름차순으로 정렬한다.
2. 중복되는 원소를 추출하는 것이므로, 같은 값이면 push해주고 두 배열의 포인터값을 증가시켜준다. 같은 값이 아니라면, 작은 값에 해당하는 배열의 포인터를 증가시켜준다. (두 배열 모두, 오름차순으로 정렬이 돼 있는 상태이므로, 작은 값에 있는 배열의 포인터를 증가시켜서 큰 값까지 가게 해야함)

3. 정답

        <script>
            function solution(arr1, arr2){
                let answer=[];
                arr1.sort((a, b)=>a-b);
                arr2.sort((a, b)=>a-b);
                let p1=p2=0;
                while(p1<arr1.length && p2<arr2.length){ //중복된 원소를 찾아서 추출하는 것이므로, 한 배열이 끝나면 더이상 중복된 원소는 없기 때문에 조건을 이렇게만 둔다.
                    if(arr1[p1]==arr2[p2]){
                        answer.push(arr1[p1++]);
                        p2++;
                    }
                    else if(arr1[p1]<arr2[p2]) p1++;
                    else p2++;
                }              
                return answer;
            }
            let a=[1, 3, 9, 5, 2];
            let b=[3, 2, 5, 7, 8];
            console.log(solution(a, b));
        </script>

//이렇게 할 수도 있구나 indexOf!
     function solution(arr1, arr2) {
        let answer = [];
        for (let i = 0; i < arr1.length; i++) {
          const findIdx = arr2.indexOf(arr1[i]);
          findIdx === -1 ? null : answer.push(arr1[i]);
        }
        return answer.sort((a, b) => a - b);
      }