교집합(투포인터 알고리즘, MS인터뷰) / c / 제한시간 : 1초

▣ 문제

두 집합 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

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>
int arr1[30000];
int arr2[30000];
int res[30000];

int main() {
	int n, m, i, j;
	int p1 = 0, p2 = 0, p3 = 0;
	int temp;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr1[i]);
	scanf("%d", &m);
	for (i = 0; i < m; i++) scanf("%d", &arr2[i]);
	for (i = 1; i < n; i++) {
		temp = arr1[i];
		for (j = i - 1; j >= 0; j--) {
			if (arr1[j] > temp)
				arr1[j + 1] = arr1[j];
			else break;
		}
		arr1[j + 1] = temp;
	}
	for (i = 1; i < m; i++) {
		temp = arr2[i];
		for (j = i - 1; j >= 0; j--) {
			if (arr2[j] > temp)
				arr2[j + 1] = arr2[j];
			else break;
		}
		arr2[j + 1] = temp;
	}


	while (p1 < n && p2 < m) {
		if (arr1[p1] == arr2[p2]) {
			res[p3++] = arr1[p1];
			p1++;
			p2++;
		}
		else if (arr1[p1] < arr2[p2]) {
			p1++;
		}
		else p2++;
	}

	for (i = 0; i < p3; i++) printf("%d ", res[i]);

	return 0;
}

우선, arr1과 arr2를 삽입정렬로 오름차순으로 정렬을 한다.

 

만약 입력 예시를 예로 들면, arr1과 arr2는 각각 다음과 같이 정렬이 된다.

2

3

5

7

10

3

5

10

12

17

 

이때, p1과 p2는 각 배열의 커서를 나타내며 초기값은 0으로 설정한다.

 

서로 배열을 비교하며 같은 숫자가 나올 경우 res 배열에 저장을 한다.

 

만약 서로 다른 숫자를 비교하면 작은 숫자를 가지고 있는 배열의 포인터를 ++ 해준다.

 

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
int arr1[30000];
int arr2[30000];
int res[30000];

int compare(const void* n1, const void* n2) {
	if (*(int*)n1 > * (int*)n2)
		return 1;
	else if (*(int*)n1 < *(int*)n2)
		return -1;
	else return 0;
}

int main() {
	int n, m, i, j;
	int p1 = 0, p2 = 0, p3 = 0;
	int temp;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr1[i]);
	qsort(arr1, n, sizeof(int), compare);
	scanf("%d", &m);
	for (i = 0; i < m; i++) scanf("%d", &arr2[i]);
	qsort(arr2, m, sizeof(int), compare);

	while (p1 < n && p2 < m) {
		if (arr1[p1] == arr2[p2]) {
			res[p3++] = arr1[p1];
			p1++;
			p2++;
		}
		else if (arr1[p1] < arr2[p2]) {
			p1++;
		}
		else p2++;
	}

	for (i = 0; i < p3; i++) printf("%d ", res[i]);

	return 0;
}

삽입정렬 대신 qsort를 사용해서 알고리즘을 더 효과적으로 짤 수 있다.

 

.

 

c언어로 짤때는 qsort의 compare 함수를 외우지 않는 이상 바로 쓰기 어려울듯함

 

c++의 경우 #include<algorithm> 에서 sort함수를 바로 쓸수있음.