[효율성/투포인터스 알고리즘] 공통 원소 구하기

문제

 

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

▣ 입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다. 각 집합의 원소는 1,000,000,000이하의 자연수입니다.

▣ 출력설명
두 집합의 공통원소를 오름차순 정렬하여 출력합니다.

▣ 입력예제 1 5
13952
5

32578

▣ 출력예제 1 235

---

결과

O

내가 푼 방식

//[공통원소 구하기]
const solution = (arr1, arr2) => {
  let answer = [];
for(let i=0; i < arr1.length; i++) {
	for(let k=0; k < arr2.length; k++) {
  	if(arr1[i] === arr2[k]) {
      answer.push(arr2[k])
    }
	}	  
}
return answer.sort((a,b) => a-b);
}

soluti on([1,3,9,5,2], [3,2,5,7,8]);

 접근과정

1. 두 번의 반복문을 통해 같은 요소의 경우 푸쉬시키고 리턴 시 sort해준다. 

---

모범답안

 

            function solution(arr1, arr2){
                let answer=[];
                arr1.sort();
                arr2.sort();
                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;
            }

리뷰

저번 문제와 마찬가지로 반복문으로 푸는 것보다 투포인터스로 푸는 것이 시간 복잡도상 효율적인 문제이다.