A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출해 오름차순으로 출력하는 프로그램을 작성하세요.
두 집합의 공통원소를 오름차순 정렬해 출력한다.
투포인터 알고리즘
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다.
- 정렬되어 있는 두 리스트의 합집합에도 사용된다. 병합정렬(merge sort)의 conquer 영역의 기초가 된다.
출처 더 보기
function solution(arr1, arr2) {
let answer = [];
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
if (arr1[i] === arr2[j]) {
answer.push(arr1[i]);
}
}
}
return answer.sort((a, b) => a - b);
}
const arr1 = [1, 3, 9, 5, 2];
const arr2 = [3, 2, 5, 7, 8];
console.log(solution(arr1, arr2));
function solution(arr1, arr2) {
let answer = [];
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
const n = arr1.length;
const m = arr2.length;
let p1=p2=0;
while (p1 < n && p2 < m) {
if (arr1[p1] === arr2[p2]) {
answer.push(arr1[p1++]);
p2++
}
else if (arr1[p1] < arr2[p2]) p1++;
else p2++;
}
return answer;
}
const arr1 = [1, 3, 9, 5, 2];
const arr2 = [3, 2, 5, 7, 8];
console.log(solution(arr1, arr2));