백준 1269번[C] - 상세 풀이

https://www.acmicpc.net/problem/1269

1269번: 대칭 차집합

---

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int A, B, cnt = 0, sum = 0;

    scanf("%d %d", &A, &B);

    int *setA = (int*)malloc(sizeof(int) * A);
    int *setB = (int*)malloc(sizeof(int) * B);

    for(int i = 0; i < A; i++) {
        scanf("%d", &setA[i]);
    }
    for(int i = 0; i < B; i++) {
        scanf("%d", &setB[i]);
    }

    // 정렬
    qsort(setA, A, sizeof(int), compare);
    qsort(setB, B, sizeof(int), compare);

    // 차집합 계산
    int i = 0, j = 0;

    while (i < A && j < B) {
        if (setA[i] < setB[j]) {
            sum++;
            i++;
        } else if (setA[i] > setB[j]) {
            sum++;
            j++;
        } else {
            i++;
            j++;
        }
    }

    // 나머지 원소 처리
    sum += A - i + B - j;

    printf("%d", sum);

    free(setA);
    free(setB);

    return 0;
}

 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 합니다. 
 문제를 풀기 위해선 각각의 집합의 차집합을 구해야합니다. 코드 순서대로 풀이를 해보자면 집합 A, B의 원소의 개수를 입력받고 배열 "setA"와 배열 "setB"에 동적으로 메모리를 할당합니다. 그 다음, qsort 함수와 compare 함수를 이용하여 집합 A와 B를  오름차순으로 정렬합니다.
while 루프를 풀이해보자면  i와 j는 각각 setA와 setB의 인덱스를 나타냅니다. 현재 각각의 집합의 원소는 오름차순으로 정렬되어 있기 때문에 만약 setA[i]가 setB[j]보다 작으면, 이는 집합 A에만 있는 원소이므로 sum을 증가시키고 i를 증가시킵니다. 반대로, 만약 setA[i]가 setB[j]보다 크면, 이는 집합 B에만 있는 원소이므로 마찬가지로 sum을 증가시키고 j를 증가시킵니다. 두 원소가 같으면, 이는 두 집합에 모두 존재하는 원소이므로 sum을 증가시키고 i와 j를 각각 증가시킵니다.
이 과정을 통해 두 집합의 차집합을 계산하고, 각 원소를 한 번씩만 세며 sum에 그 개수를 저장하게 됩니다. 이후에 남은 집합의 원소들은 그 집합에만 있는 원소가 되므로 sum에 추가로 더해주어야 제대로 값을 구할 수 있게됩니다.