백준 1822 차집합 문제풀이 (JAVA)

문제 링크

문제

몇 개의 자연수로 이루어진 두 집합 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만을 출력하면 된다.

풀이

지금 보니까 그냥 HashSet으로도 풀리지 않았을까....
A와 B를 각각 ArrayList에 대입한 후 오름차순으로 정렬했다.
순차적으로 하나씩 꺼내서 만약 A의 값 보다 B의 값이 더 크면 A의 값은 B에 없는 것이므로 출력한다.
그렇지 않고, A의 값이 B의 값보다 크다면 B의 다음 값을 가져와서 재비교 해본다.
만약 같으면 패스한다.

소스코드

import java.util.*;
import java.io.*;
public class Main{
    
    public static void main(String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int NUMBER_OF_A = Integer.parseInt(st.nextToken());
        final int NUMBER_OF_B = Integer.parseInt(st.nextToken());
        
        ArrayList<Integer> listA = new ArrayList<Integer>();
        ArrayList<Integer> listB = new ArrayList<Integer>();
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<NUMBER_OF_A;i++) {
            
            listA.add( Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<NUMBER_OF_B;i++) {
            listB.add( Integer.parseInt(st.nextToken()));
        }
        Collections.sort(listA);
        Collections.sort(listB);
        
        int count = 0;
        ArrayList<Integer> answer = new ArrayList<Integer>();
        int pivot = 0;
        for(int i=0;i<NUMBER_OF_A;i++) {
            if(pivot != NUMBER_OF_B) {
                if(listA.get(i) < listB.get(pivot)) {
                    answer.add(listA.get(i));
                    count++;
                }else if (listA.get(i) > listB.get(pivot)){
                    pivot++;
                    i--;
                }else {
                    pivot++;
                }
            }else {
                answer.add(listA.get(i));
                count++;
            }
           
        }
        sb.append(count);
        sb.append("\n");
        for(Integer k : answer) {
            sb.append(k);
            sb.append(" ");
        }
        sb.append("\n"); 
        
        bw.write(sb.toString());
        
        bw.flush();
        br.close();
        bw.close();
        
    }

    
}