1269번: 대칭 차집합

 

- 문제 사이트: https://www.acmicpc.net/problem/1269

1269번: 대칭 차집합

 

자연수를 원소로 갖는 집합 A 와 집합 B가 주어졌을 때, 두 집합의 대칭 차집합 원소의 개수를 출력하는 문제이다.

예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때,  A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.

 

A와 B의 원소를 비교해주며 공통 원소가 아닌 경우만 개수를 카운팅해주도록 계산했다.

 

1) 입력받은 A 와 B 원소 오름차순으로 정렬

2) 각각 첫번째 원소부터 값 비교: idxA = idxB = 0 부터 1씩 증가하며 원소를 비교

3-1) 같은 값인 경우, 카운팅하지 않음

3-2) A 원소의 값이 더 큰 경우, 다음 B의 원소와 비교: idxB++ && 카운팅

3-3) B 원소의 값이 더 큰 경우, 다음 A의 원소와 비교: idxA++ && 카운팅

4) 비교 가능한 모든 원소를 비교 완료한 경우, 남은 원소의 개수 카운팅

 

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int sizeA, sizeB;
    cin >> sizeA >> sizeB;
    
    int a[sizeA];
    for (int i = 0; i < sizeA; i++)
        cin >> a[i];

    int b[sizeB];
    for (int i = 0; i < sizeB; i++)
        cin >> b[i];
    
    sort(a, a + sizeA);
    sort(b, b + sizeB);
    
    int idxA = 0;
    int idxB = 0;
    int result = 0;
    while (idxA < sizeA && idxB < sizeB)
    {
        if (a[idxA] == b[idxB])
        {
            idxA++;
            idxB++;
        }
        else if (a[idxA] > b[idxB])
        {
            idxB++;
            result++;
        }
        else
        {
            idxA++;
            result++;
        }
    }

    result += (sizeA - idxA + sizeB - idxB);
    cout << result << "\n";
    return 0;
}

- 메모리: 3456 KB

- 시간: 236 ms

- 코드 길이: 802 B

 

단순 개수만 카운팅하는 것이므로 vector의 중복 원소를 확인해주는 unique 함수를 이용하여 계산해줄 수도 있다.

 

1) 전체 원소를 하나의 벡터로 입력 받음 = (A만 갖고 있는 원소 + 중복 원소) + (B만 갖고 있는 원소 + 중복 원소)

2) 원소 오름차순으로 정렬

3) 중복 원소 확인하여 개수 계산

4) 전체 원소 개수에서 중복 원수 개수를 두번 빼준 값 출력

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int sizeA, sizeB;
    cin >> sizeA >> sizeB;
    
    int totalSize = sizeA + sizeB;
    vector<int> arr(totalSize);
    for (int i = 0; i < totalSize; i++)
        cin >> arr[i];
    
    sort(arr.begin(), arr.end());
    int intersection = arr.end() - unique(arr.begin(), arr.end());
    int result = totalSize - (intersection * 2);
    cout << result << "\n";
    return 0;
}

- 메모리: 3584 KB

- 시간: 224 ms

- 코드 길이: 476 B

 

set_intersection와 back_inserter 함수를 이용해 직접 교차 집합 원소를 구해줄 수도 있다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int sizeA, sizeB;
    cin >> sizeA >> sizeB;
    
    vector<int> a(sizeA);
    for (int i = 0; i < sizeA; i++)
        cin >> a[i];
        
    vector<int> b(sizeB);
    for (int i = 0; i < sizeB; i++)
        cin >> b[i];
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<int> intersection;
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(intersection));

    cout << sizeA + sizeB - (intersection.size() * 2) << "\n";
    return 0;
}

- 메모리: 4912 KB

- 시간: 232 ms

- 코드 길이: 589 B