백준 1822번 : 차집합 (C 언어)

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

1822번: 차집합

Code:

#include <stdio.h>
#include <stdlib.h>
 
int compare(const void* a, const void* b)
{
    if (*(int*)a > *(int*)b) return 1;
    else if (*(int*)a < *(int*)b) return -1;
    else return 0;
}
 
long long binarySearch(int arr[], long long target, long long left, long long right)
{
    while (left <= right) {
        long long mid = (left + right) / 2;
 
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
 
    return -1;
}
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int arrn[500001] = { 0, };
    int arrm[500001] = { 0, };
    int check[500001] = { 0, };
    int flag = 0;
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arrn[i]);
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &arrm[i]);
    }
    for (int i = 0; i < n; i++)
    {
        long long index = binarySearch(arrm, arrn[i], 0, m);
        if (index == -1)
        {
            check[count++] = arrn[i];
        }
    }
    if (count == 0)
    {
        printf("0");
    }
    else
    {
        qsort(check, count, sizeof(int), compare);
        printf("%d\n", count);
        for (int i = 0; i < count; i++)
        {
            printf("%d ", check[i]);
        }
    }
    return 0;
}

문제 설명

문제: 집합 A에는 속하면서 집합 B에는 속하지 않는 원소 구하기

주어진 문제는 두 개의 집합 A와 B가 주어졌을 때, 집합 A에 속하면서 집합 B에는 속하지 않는 원소를 구하는 문제입니다. 집합 A와 B는 자연수로 이루어져 있으며, 원소의 개수에는 제한이 있습니다. 이를 해결하기 위해 C 언어를 사용하여 프로그램을 작성해보겠습니다.

---

코드 설명

 

1. 필요한 라이브러리를 포함시킵니다.
2. compare 함수를 정의합니다. 이 함수는 qsort 함수에서 사용될 비교 함수입니다.
3. binarySearch 함수를 정의합니다. 이 함수는 이진 검색을 수행하여 배열에서 원하는 값을 찾습니다.
4. main 함수에서 변수 및 배열을 선언합니다. 그리고 집합 A와 B를 입력받습니다.
5. 집합 B를 정렬합니다.
6. 이진 검색을 통해 집합 A에 속하면서 집합 B에 속하지 않는 원소를 찾아 check 배열에 저장합니다.
7. count 변수를 확인하여 결과를 출력합니다. 원소가 없는 경우 0을 출력하고, 원소가 있는 경우 정렬하여 출력합니다.
8. 동적 할당한 배열을 해제합니다.

이렇게 작성된 코드를 실행하면 주어진 문제에 맞게 집합 A에 속하면서 집합 B에 속하지 않는 원소를 구할 수 있습니다.