차집합을 구하는 프로그램

집합 A와 집합 B의 원소들이 오름차 순으로 정렬되어 있다고 가정하고 문제를 풀어본다.

---------------------------------------------------------------------------------------------------------------------------------

차집합 C를 초기화한다. (원소의 갯수가 0)

집함 A와 집합 B의 마지막에 무한대의 원소 1개를 각각 삽입하여 준다. 

(프로그램을 간단히 하기 위해서)

a := A의 첫원소를 제거

b := B의 첫원소를 제거

while (A의 원소가 있을 때)

       만약 a 가 작으면 

             a를 차집합 C에 넣는다.

             a:= A의 첫원소를 제거

       만약 b 가 작으면

             b:= B의 첫원소를 제거

       만약 a와 b가 같다면

             // A의 원소도 무조건 있다

             a := A의 첫원소를 제거

             // B의 원소는 무조건 있다.

             b := B의 첫원소를 제거

아주 멋진 코드가 되었다.

#include <stdio.h>

void diff(int A[], int B[], int C[]) {

    int a, b, i, j, k, max;

    

    max=A[0]+1;

    A[A[0]+1]=10000;        

    B[B[0]+1]=10000;

    i=j=1;

    k=0;

    a=A[i++];

    b=B[j++];

    while(i<max+1) {

        if(a<b) {

            C[++k]=a;

            a=A[i++];

        }

        else if(a>b) b=B[j++];

        else {

            a=A[i++];

            b=B[j++];

        }

    }

    C[0]=k; 

    A[A[0]+1]=0; B[B[0]+1]=0; // 다시 0을 넣어 준다.

}

int main() {

    int A[100]={9,1,2,3,4,5,6,7,8,9,};    // A[0] 에는 갯수 9가 들어 있다.

    int B[100]={4,2,3,7,10,};                // B[0] 에는 갯수 4가 들어 있다.

    int C[100]={0,};                             // C[0] 에는 갯수 0이 들어 있다.

    int i;

    diff(A, B, C);

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

    return 0;

}