[BOJ][C++] 백준 1296번: 대칭 차집합

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

1269번: 대칭 차집합

 

문제

자연수를 원소로 갖는 공집합이 아닌 두 집합 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을 넘지 않는다.

출력

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

 

풀이

쉬운 문제라고 생각해서 배열을 이용했으나 배열의 크기가 너무 컸기 때문인지 메모리 초과가 뜬다

#include <iostream>
#include <vector>

using namespace std;

const int INF = 100000000;

int main() {
    vector<int> number(INF, 0);
    int n,m, k;
    cin >> n >> m;
    for(int i=0; i<n+m; i++) {
        cin >> k;
        number[k]++;
    }
    
    int ans=0;
    for(int i=0; i<INF; i++) {
        if(number[i] == 1) {
            ans++;
        }
    }
    cout << ans;
    
    return 0;
}

 

https://www.acmicpc.net/board/view/24015

글 읽기 - 메모리 초과... 128 mb이면 int형 몇개?까지 선언가능한가요??

 

본 문제의 메모리 제한은 256mb로 1mb당 정수 26만개 정도만 저장 가능하다는걸 감안하면 약 6천만개의 정수만 저장 가능하다

위 코드에서는 배열에 정수를 10억개 저장하려 하니 턱없이 모자라다

 

메모리 낭비를 줄이기 위해 set 자료구조를 이용했다

 

#include <iostream>
#include <set>

using namespace std;

const int INF = 100000000;

int main() {
    set<int> set;
    int n,m, k;
    cin >> n >> m;
    for(int i=0; i<n+m; i++) {
        cin >> k;
        auto iter = set.find(k);
        if(iter != set.end()) {
            set.erase(iter);
        } else {
            set.insert(k);
        }
    }
    
    cout << set.size();

    return 0;
}