문제
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
문제 풀이
예습이론
sort() 주의사항: 그냥 sort()를 하면, 문자로 변환 후 정렬한다. 이를 방지하기 위해, 매개변수에 콜백함수를 넣어줘야한다. (콜백함수는 정렬기준이 된다.) 아래 예제에서 sort()의 매개변수가 없기 때문에, 문자로 인식하고 사전순 정렬을 하게된다. 따라서, 잘못된 정렬이 나온다. (10이 앞에 1이 있기 때문에 앞에 정렬되었다.)
*sort의 이론은 다른 예제 참고
a=[1, 3, 10, 5, 2];
a.sort();
console.log(a);
>>[1, 10, 2, 3, 5] 코드
투포인터 알고리즘을 활용해서 풀 수 있는 문제이다. 따라서, 시간복잡도는 O(n+m)이다.
(1) arr1과 arr2를 오름차순으로 정렬한다.
(2) arr1을 가리키는 p1과, arr2를 가리키는 p2를 만든다.
(3) arr1[p1]===arr[p2]라면, answer에 push한다. 그리고 두 포인터의 위치를 옮긴다(+1)
만약 arr1[p1]<arr2[p2]라면, p1++
아니라면(arr2[p2]<arr1[p1]) p2++
(4) answer을 리턴한다.
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<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>
</body>
</html>
9/12
반드시 먼저 arr1, arr2의 정렬을 해주어야한다.