[Java] 백준 1822

1822. 차집합 (Silver 4) 

# 자료구조

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

 

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

 

예제 입력 1

4 3
2 5 11 7
9 7 4

예제 출력 1

3
2 5 11

 

예제 입력 2

3 5
2 5 4
1 2 3 4 5

예제 출력 2

0

 

문제를 풀기 위해 자동으로 오름차순 정렬을 해주는 동적 배열인 TreeSet을 사용해줬다.

그 다음 집합 a의 원소 개수와 집합 b의 원소 개수를 차례로 입력 받고, 입력받은 집합 a의 원소 개수만큼 a의 원소를 d_set에 담았다.

집합 b의 원소 개수만큼 해당 원소를 입력받았는데, if문과 contains를 사용해서 만약 a집합에서 입력받은 원소와 중복되는 것이 있다면 해당 원소를 remove를 사용해서 삭제해줬다.

마지막으로 배열의 크기를 size를 사용해서 출력해주었고, d_set에 있는 원소들을 출력해주었다.

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num_a, num_b;
        int overlap;
        TreeSet<Integer> d_set = new TreeSet<Integer>();

        num_a = sc.nextInt();    // 집합 a 원소 개수
        num_b = sc.nextInt();    // 집합 b 원소 개수

        for (int i = 0; i < num_a; i++) 
            d_set.add(sc.nextInt());    // a 원소 d_set 배열에 담기
        
        for (int j = 0; j < num_b; j++) {
            overlap = sc.nextInt();   // 원소 b에 담길 원소 입력 받음
            if (d_set.contains(overlap)) {    // 만약 a 집합과 중복되는 게 있으면 
                d_set.remove(overlap);        // 해당 원소 삭제
            }
        }
        System.out.println(d_set.size()); // 배열(차집합)의 크기 출력

        for (Integer n : d_set) {
            System.out.print(n + " ");
        }
    }
}

자바로 백준 문제는 처음 제출해봐서 class이름을 Main으로 하는 걸 몰랐던지라 엄청 많이 컴파일에러가 났다.......