[백준] 1822번. 차집합(JAVA)

문제

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

---

풀이(7분)

import java.util.*;
import java.io.*;

class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;


        st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        Set<Integer> set = new TreeSet<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < A; i++){
            set.add(Integer.parseInt(st.nextToken())); // A의 모든 원소 추가
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < B; i++){
            int num = Integer.parseInt(st.nextToken()); 
            set.remove(num); // A에 중복된다면 삭제
        }

        StringBuilder sb = new StringBuilder();
        if(set.size() == 0){
            System.out.println(0);
            return;
        }

        sb.append(set.size()).append("\n");
        for(int i : set){
            sb.append(i).append(" ");
        }

        System.out.println(sb);

    }
}

---

문제 풀이 전략

 

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcSdMulGJVfeRYN7MSv5P-3xwmfRZBwMgUVMyQ&s

 

차집합은 위와 같은 벤다이어그램으로 나타난다.

 

그렇다면 어려운 고민 없이 두 교집합을 구한 뒤 B를 전부 제외해 주면 된다!

 

코드를 보면 하나의 집합(TreeSet)을 이용하여 모든 원소를 넣고 빼준 것이다.

 

✅ 체크 포인트 

1. 오름차순으로 출력해야하므로 TreeSet을 이용하자.

2. set.contains()를 하지 않고, remove()를 해도 된다! 있는 경우에만 빠진다.