백준 1822 차집합

문제

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

---

코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        int nA=Integer.parseInt(st.nextToken());
        int nB=Integer.parseInt(st.nextToken());
        int[] arrayA=new int[nA];
        int[] arrayB=new int[nB];

        s=br.readLine();
        st=new StringTokenizer(s);
        for(int i=0; i<nA; i++)
            arrayA[i]=Integer.parseInt(st.nextToken());

        s=br.readLine();
        st=new StringTokenizer(s);
        for(int i=0; i<nB; i++)
            arrayB[i]=Integer.parseInt(st.nextToken());
        Arrays.sort(arrayB);

        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for(int i:arrayA){
            if(Arrays.binarySearch(arrayB, i)<0)
                pq.add(i);
        }

        if(pq.isEmpty())
            bw.write("0\n");
        else{
            bw.write(pq.size()+"\n");
            while(!pq.isEmpty())
                bw.write(pq.remove()+" ");
        }

        bw.flush();
    }
}

---

해결 과정

1. arrayA, arrayB를 모두 입력받은 뒤 A 배열의 요소를 arrayB에서 Linear Search 해서 result 배열에 저장하고 출력했다.

2. 시간초과 (B 배열을 Arrays.sort 하고 Binary Search를 돌린 뒤 Priority Queue로 오름차순으로 출력해야 한다, 문제를 똑바로 안 읽었다...)

3. 😁