[백준 1269] 대칭 차집합 - JAVA

 

1. 문제 해석

문제에 따르면 A 집합과 B 집합이 다음과 같은 형태로 존재할 때

 

A와 B 집합의 다이어그램

이들의 대칭 차집합은 아래와 같습니다.

 

A와 B 집합의 대칭 차집합

 

위와 같은 형태로 집합을 구하고, 그 집합의 원소의 개수를 구하면 되는 간단한 문제입니다. 

 

Bit-string으로 표현되는 Set을 이용하기로 했습니다. Set을 Bit-string으로 표현하면 전체 집합의 크기가 N일 때, 각 집합을 N bit로 표현하고, 원소가 집합에 포함되어 있으면 해당 bit를 1로, 그렇지 않으면 0으로 표현하게 됩니다.

 

예를 들어서 10bit로 집합 A = {1, 3, 5, 7, 9}를 표현하면 아래와 같습니다.

 

Bit-string representation of sets

 

어떤 원소가 집합 A에 속하는지 확인할 때는 value가 1인지 아닌지만 확인하면 되고 원소의 삽입과 삭제는 해당 bit를 1 또는 0으로 설정하면 됩니다.

 

원소 1 Insertion 및 원소 5 Deletion

 

합집합과 차집합은 각각 bit-or 연산 및 bit-and 연산을 수행하면 쉽고 빠르며, 차집합을 구할 때는 첫 번째 집합 String과 두 번째 집합 String의 보수를 and 연산하면 됩니다.

 

 

A∪B 와  A∩B

 

이와 같은 자료형을 JAVA에서 라이브러리로 제공하고 있으므로 코드는 간단하게 구현할 수 있습니다.

 

2. 코드

JAVA에서 BitSet 라이브러리를 import 해서 사용합니다. BitSet은 다양한 메소드를 제공하며 이 문제에서는 아래의 메소드들 만으로 충분히 해결할 수 있습니다.

 

메서드	설명
BitSet() BitSet(int nbits)	초기에 비트 64개나 nbits개를 담을 수 있는 비트 집합을 생성한다.
void set(int bitIndex) void set(int fromIndex, int toIndex) void set(int bitIndex, boolean value) void set(int fromIndex, int toIndex, boolean value)	지정한 인덱스나 fromIndex(포함)에서 toIndex(미포함) 사이에 있는 비트를 1이나 지정한 값으로 설정한다.
void and(BitSet set) void andNot(BitSet set) void or(BitSet set) void xor(BitSet set)	set과 교집합, 차집합, 합집합, 대칭 차집합을 형성한다.
int cardinality()	비트 집합에 있는 1비트들의 개수를 반환한다. ※ 주의: size 메서드는 집합 크기가 아닌 비트 벡터(bit vector)의 현재 크기를 반환한다.

 

코드로 바로 확인해보겠습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.StringTokenizer;

public class XorSet_1269 {
	// 입력되는 원소의 최댓값
    private final static int MAX = 100000000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(tokens.nextToken());
        int M = Integer.parseInt(tokens.nextToken());

        BitSet setA = new BitSet(MAX);
        BitSet setB = new BitSet(MAX);

        // 집합 A에 원소 입력
        tokens = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int bitIdx = Integer.parseInt(tokens.nextToken());
            setA.set(bitIdx, true);
        }

        // 집합 B에 원소 입력
        tokens = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int bitIdx = Integer.parseInt(tokens.nextToken());
            setB.set(bitIdx, true);
        }

        // 대칭 차집합을 구함
        setA.xor(setB);
        // 연산 결과, 집합 A, B의 대칭 차집합의 원소 개수
        int result = setA.cardinality();

        // 출력
        System.out.println(result);
    }
}

 

3. 결과

 

4. 참고

BitSet 클래스의 메서드

https://thebook.io/006985/ch07/05/02-01/

가장 빨리 만나는 코어 자바 9: 7.5.2 비트 집합 - 1