배열의 합집합(Union)은 두 배열에 속한 모든 원소를 중복 없이 하나로 모은 집합을 의미합니다. 이 글에서는 C 언어를 활용해 두 개의 배열에 대해 합집합 연산을 수행하는 방법을 예제 코드와 함께 단계별로 살펴보겠습니다.
합집합 연산이란?
예를 들어 다음과 같은 두 개의 배열이 있다고 가정해 보겠습니다.
- 배열 1 = {1, 2, 3, 4, 6}
- 배열 2 = {1, 2, 5, 6, 7}
두 배열의 합집합은 다음과 같이 구할 수 있습니다.
배열1 ∪ 배열2 = {1, 2, 3, 4, 6} ∪ {1, 2, 5, 6, 7} = {1, 2, 3, 4, 5, 6, 7}
즉, 중복된 원소를 제거하고 모든 원소를 한 번씩만 담은 집합이 바로 합집합입니다.
합집합 구현 로직
1단계: 두 배열을 하나로 합치기
첫 번째 배열과 두 번째 배열의 원소를 순서대로 결과 배열(uni)에 복사합니다.
for(i=0;i<size1;i++){
uni[j]=a[i];
j++;
}
for(i=0;i<size2;i++){
uni[j]=b[i];
j++;
}2단계: 중복 원소 제거하기
합쳐진 배열에서 서로 같은 값을 가지는 원소를 찾아 제거합니다. 중복이 발견되면 해당 위치부터 뒤에 있는 원소들을 한 칸씩 앞으로 당겨 배열의 크기를 줄여나가는 방식입니다.
int removerepeated(int size,int a[]){
int i,j,k;
for(i=0;i<size;i++){
for(j=i+1;j<size;){
if(a[i]==a[j]){
for(k=j;k<size;k++){
a[k]=a[k+1];
}
size--;
}else{
j++;
}
}
}
return(size);
}C 프로그램 전체 코드
다음은 두 배열에 대해 합집합 연산을 수행하는 완전한 C 프로그램입니다. 사용자로부터 두 배열의 크기와 원소를 입력받은 뒤, 병합 → 정렬 → 중복 제거 과정을 거쳐 최종 합집합을 출력합니다.
#include<stdio.h>
int removerepeated(int size,int a[]);
void sort(int size,int a[]);
main(){
int i,size1,size2,size,j=0,k;
printf("Enter size of an array1\n");
scanf("%d",&size1);
printf("Enter size of an array2\n");
scanf("%d",&size2);
int a[size1],b[size2],uni[size1+size2];
printf("Enter numbers for array 1\n");
for(i=0;i<size1;i++){
scanf("%d",&a[i]);
}
printf("Enter numbers for array 2\n");
for(i=0;i<size2;i++){
scanf("%d",&b[i]);
}
// 합집합 시작
for(i=0;i<size1;i++){
uni[j]=a[i];
j++;
}
for(i=0;i<size2;i++){
uni[j]=b[i];
j++;
}
// 정렬
sort(size1+size2,uni);
// 중복 원소 제거
size=removerepeated(size1+size2,uni);
printf("Array after Union \n");
for(i=0;i<size;i++){
printf("%d\n",uni[i]);
}
}
int removerepeated(int size,int a[]){
int i,j,k;
for(i=0;i<size;i++){
for(j=i+1;j<size;){
if(a[i]==a[j]){
for(k=j;k<size;k++){
a[k]=a[k+1];
}
size--;
}else{
j++;
}
}
}
return(size);
}
void sort(int size,int a[]){
int i,j,temp;
for(i=0;i<size;i++){
for(j=i+1;j<size;j++){
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
Enter size of an array1 4 Enter size of an array2 3 Enter numbers for array 1 1 2 3 4 Enter numbers for array 2 3 5 6 Array after Union 1 2 3 4 5 6
프로그램 동작 흐름 정리
- 두 배열의 크기와 각 원소를 사용자로부터 입력받습니다.
- 두 배열의 모든 원소를 하나의 배열(uni)에 차례대로 복사하여 병합합니다.
- 병합된 배열을 오름차순으로 정렬합니다.
- 중복된 원소를 제거하여 최종 합집합을 완성합니다.
- 결과 배열을 화면에 출력합니다.
이처럼 배열 병합, 정렬, 중복 제거라는 세 가지 기본 연산만 조합하면 별도의 라이브러리 없이도 간단하게 합집합을 구현할 수 있습니다. 시간 복잡도를 개선하고 싶다면 정렬 후 인접 원소만 비교하거나 해시 테이블을 활용하는 방법도 고려해 볼 수 있습니다.