대칭 차집합 실패

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

13954

8571

7077

62.281%

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 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의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

출력

첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

예제 입력 1 복사

3 5
1 2 4
2 3 4 5 6

예제 출력 1 복사

이미 저번에 한 번 풀어보고 실패한 문제이나 이번에는 보자마자 풀이과정이 쉽게 떠올랐다.

그렇다면 나는 왜 풀지 못한 것일까?

또 습관처럼 O(n^2) 알고리즘을 써버렸기 때문이다.

숫자 제한을 보지 않은 것이 패착이다.

집합 크기가 최대 200000이기 때문에 200000^2=400억의 연산횟수가 필요하다. 즉 나의 알고리즘은 일반적인 컴퓨터로 400초는 걸리는 알고리즘이었다.

그래서 나는 또 습관처럼 아무렇게나 이진탐색 함수를 썼다.

정렬되지 않은 숫자에 말이다.

멍청하게도 나는 코드를 처음부터 끝까지 5번 넘게 보고도 원인을 찾지 못했다.

그리고 드디어 6번째에 찾았다.

그러나 안타깝게도 이진탐색트리는 내가 아직 만들 줄 모른다.

그렇기 때문에 이 문제의 탐색 sollution은 다음으로 미루는 것으로 할 것이고. 틀린 코드를 포스팅 해놓겠다.

요새 많은 문제들이 나중으로(?) 밀리고 있다.

내일부터는 밀린 문제를 푸는 것에 주력해야겠다.

밀린 문제는 혼자 풀겠다고 미련하게 끙끙대지 말고 제한시간 안에 안풀리면 시원하게 풀이를 볼 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<iostream>
#include<string>
int BSearch(int arr[], int len, int target)
{
    int first = 0;
    int last = len - 1;
    int mid;
 
    while (first <= last)
    {
        mid = (first + last) / 2;
 
        if (target == arr[mid])
        {
            return mid;
        }
        else
        {
            if (target < arr[mid]) { last = mid - 1; }
            else
            {
                first = mid + 1;
            }
        }
    }
    return -1;
}
void MINUS(int* par1, int par1_size, int* par2, int par2_size)
{
    int var;
    for (int i = 0; i < par2_size; i++)
    {
        var = BSearch(par1, par1_size, par2[i]);
        if (var != -1)
        {
            par1[var] = 0;
        }
    }
    return;
}
 
int main()
{
    int* arr1;
    int* original_arr1;
    int arr1_size;
    int* arr2;
    int arr2_size;
    std::cin >> arr1_size >> arr2_size;
 
    arr1 = new int[arr1_size];
    arr2 = new int[arr2_size];
    original_arr1 = new int[arr1_size];
 
    for (int i = 0; i < arr1_size; i++)
    {
        std::cin >> arr1[i];
        original_arr1[i] = arr1[i];
    }
 
    for (int i = 0; i < arr2_size; i++)
    {
        std::cin >> arr2[i];
    }
 
    MINUS(arr1, arr1_size, arr2, arr2_size);
    MINUS(arr2, arr2_size, original_arr1, arr1_size);
 
    int sum = 0;
    for (int i = 0; i < arr1_size; i++)
    {
        if (arr1[i])
        {
            sum++;
        }
    }
 
    for (int i = 0; i < arr2_size; i++)
    {
        if (arr2[i])
        {
            sum++;
        }
    }
 
    std::cout << sum;
 
    delete[]arr1;
    delete[]arr2;
    delete[]original_arr1;
}
Colored by Color Scripter
cs

sollution

MINUS(int arr1, int arr1_size, int arr2, int arr2_size) 함수에 대한 설명

두 집합을 탐색하며 arr1에 있는 숫자 중 arr2의 숫자가 같은 게 있으면 arr1의 숫자를 0으로 만들어놓는다.

간단히 말하자면 차집합 연산이다.

0은 집합의 원소로 치지 않는다. 즉 원소가 있는 인덱스에 0을 저장하면 원소를 하나 빼는 것과 같다.

main함수에 대한 설명

대칭차집합은 교집합이 없는 집합끼리의 합집합 연산이다. 따라서 합집합 연산을 따로 짤 필요 없이 sum에 arr1과 arr2의 집합 원소 개수를 더한 값을 저장해준다.
sum을 출력해준다.

[1269]대칭 차집합