문제
두 집합 A, B가 주어지면 두 집합의 교집합을 출력하는 프로그램을 작성하세요.
💡 입력설명
첫 번째 줄에 집합 A의 크기 N(1<=N<=30,000)이 주어집니다.
두 번째 줄에 N개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
세 번째 줄에 집합 B의 크기 M(1<=M<=30,000)이 주어집니다.
네 번째 줄에 M개의 원소가 주어집니다. 원소가 중복되어 주어지지 않습니다.
각 집합의 원소는 int형 변수의 크기를 넘지 않습니다.
💡 출력설명
두 집합의 교집합을 오름차순 정렬하여 출력합니다.
💡 입력예제
5
2 7 10 5 3
5
3 10 5 17 12
💡 출력예제
3 5 10
코드
첫 번째 풀이
#include <stdio.h>
#include <vector>
int a[30001], b[30001], c[61000];
int main() {
int n, m, i, j, tmp, pt1 = 1, pt2 = 1, pt3 = 1;
scanf("%d", &n);
for(i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
for(i = 1; i <= m; i++) {
scanf("%d", &b[i]);
}
// 두 배열 오름차순으로 정렬(삽입정렬)
for(i = 2; i <= n; i++) {
tmp = a[i];
for(j = i - 1; j >= 1; j--) {
if(a[j] > tmp) {
a[j + 1] = a[j];
} else {
break;
}
}
a[j + 1] = tmp;
}
for(i = 2; i <= m; i++) {
tmp = b[i];
for(j = i - 1; j >= 1; j--) {
if(b[j] > tmp) {
b[j + 1] = b[j];
} else {
break;
}
}
b[j + 1] = tmp;
}
// 투포인트 알고리즘을 이용한 교집합 찾기
while(pt1 <= n && pt2 <= m) {
if(a[pt1] == b[pt2]) {
c[pt3++] = a[pt1++];
pt2++;
} else {
if(a[pt1] < b[pt2]) {
pt1++;
} else {
pt2++;
}
}
}
for(i = 1; i < pt3; i++) {
printf("%d ", c[i]);
}
return 0;
}
최종 풀이
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, i, pt1 = 0, pt2 = 0, pt3 = 0;
scanf("%d", &n);
vector<int> a(n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &m);
vector<int> b(m);
for(i = 0; i < m; i++) {
scanf("%d", &b[i]);
}
vector<int> c(n + m);
// 퀵정렬을 통해 a, b배열 오름차순으로 정렬
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// 투포인트 알고리즘을 이용한 교집합 찾기
while(pt1 < n && pt2 < m) {
if(a[pt1] == b[pt2]) {
c[pt3++] = a[pt1++];
pt2++;
} else if(a[pt1] < b[pt2]) {
pt1++;
} else {
pt2++;
}
}
for(i = 0; i < pt3; i++) {
printf("%d ", c[i]);
}
return 0;
}
설명
사용자로부터 n, m을 입력받아 해당 크기의 만큼의 두 vector a, b를 선언한다. 이후 해당 vector에 수열을 입력받는다.
투포인트 알고리즘을 적용하기 이전에 두 vector 모두 오름차순으로 정렬되어야하므로 퀵정렬을 사용한다.
정렬 후 각 vector의 point 변수를 0으로 초기화하고 하나라도 크기에 도달할 때 까지 반복하는 while문을 작성한다.
만약 두 vector의 값이 같으면 두 vector의 point를 1씩 증가하고 해당 값을 c에 할당한다. 그렇지 않은 경우 작은 값의 point를 1씩 증가한다.
두 vector중 하나라도 크기에 도달했을 경우 교집합이 존재하지 않으므로 while문이 종료되고 마지막으로 c vector를 출력하여 마무리한다.
배운 점
투포인트 알고리즘
개념
- 리스트에 접근해야할 때 두 개의 point를 기록하면서 처리하는 알고리즘
- 정렬되어있는 두 리스트의 합집합(병합정렬), 교집합에 사용됨.
시간복잡도
포인터는 1씩 증가하고 n번까지 증가해야 알고리즘이 끝나므로 O(N)이다. (두 배열 모두 합해도 O(N))
퀵정렬 사용 법
sort(arr.begin(), arr.end());
- <algorithm>: sort()
- <vector>: arr.begin(), arr.end()
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.