집합에서 원소 빠르게 찾기, 차집합, 합집합 알고리즘 풀이 C++ / Java / 파이썬

A라는 집합과 B라는 집합이 있습니다.

각각 집합에는 수많은 원소들이 있고 서로 겹치는 원소들을 빠르게 찾으려고 합니다.

 

백준 1269번 대칭 차집합 문제를 풀어보면서 집합의 속한 원소를 빠르게 찾는 방법을 알아봅시다.

 

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

1269번: 대칭 차집합

 

집합 A에서 집합 B를 빼는 것을 차집합이라고 합니다.

A에도 있고 B에도 있는 원소를 제거하는 것이 핵심입니다.

마찬가지로 집합 B에서 집합 A를 빼려면 같은 원소를 B에서 제거합니다.

 

원소의 최대 개수가 20만개로 원소를 찾는데 O(1)의 시간복잡도로 문제를 해결해야 시간초과가 나지 않습니다.

따라서 단순 배열이 아닌 map, set, tree 등 자료구조를 활용해야 합니다.

 

1. JAVA

HashMap a, b를 각각 선언합니다.

a에 입력받은 원소를 넣습니다.

b에 속하는 원소를 입력받기전 a에 있는지 확인합니다.

a에 있으면 a에서 제거하고 없으면 b에 넣습니다.

마지막에 a와 b집합의 사이즈를 합하면 정답이 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {   
	public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
	    
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
	    
        HashMap<Integer, Integer> a = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> b = new HashMap<Integer, Integer>();
	    
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < A; i++){
            a.put(Integer.parseInt(st.nextToken()), 1);
        }
	    
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < B; i++){
            int temp = Integer.parseInt(st.nextToken());
            if(a.containsKey(temp)) {
                a.remove(temp);
            } else {
                b.put(temp, 1);
            }
        } 
        System.out.println(a.size() + b.size());
    }
}

2. C++

java와 동일하게 풀면 재미가 없죠.

좀 더 소스를 개선해 봅시다.

 

키, 밸류 자료구조까지는 필요가 없으니 키만 있는 set을 선언합니다.

그리고 a, b 두개도 필요 없습니다.

a, b 사이즈는 이미 처음부터 주어집니다.

a, b 사이즈의 합에 b를 입력 받을 때 중복되는 값만 구해서 각각 집합에서 빼주면 정답입니다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A, B;
    set<int> a;
    cin >> A >> B;

    for (int i = 0; i < A; i++) {
        int temp;
        cin >> temp;
        a.insert(temp);
    }

    int dup = 0;
    for (int i = 0; i < B; i++) {
        int temp;
        cin >> temp;
        if (a.find(temp) != a.end()) {
            dup++;
        }
    }
    cout << (A - dup) + (B - dup) << '\n';
    return 0;
}

3. 파이썬

Python은 고민할 필요도 없습니다.

a, b 집합을 만듭니다.

직관적으로 각각 차집합('-')을 구하고 그것을 합집합('|')해서 사이즈를 출력하면 답입니다.

A,B=map(int,input().split())
a=set(map(int,input().split()))
b=set(map(int,input().split()))
print(len(a-b|b-a))

집합에서 원소를 빠르게 찾는 문제를 풀어보았습니다.