[Java] 백준(실버-4) 1822번 - 차집합

문제 풀이

---

이번 문제는 이분 탐색을 이용하면 쉽게 풀 수 있다.

아이디어 도출

• 입력으로 주어지는 값을 각각 A와 B 배열에 저장한다.
• A 배열을 순회하면서 각 원소가 B 배열에 존재하는지 이분탐색으로 찾는다.
• A 배열의 원소가 B 배열의 존재하지 않는다면 이분 탐색의 결과로 음수값이 반환될텐데, 음수값일때의 A배열의 원소가 정답이 된다.

결국, 이분 탐색을 진행하여 음수가 반환되는 A 배열의 원소는 B 배열에 존재하지 않는 원소이므로, 해당되는 A 배열의 원소들을 출력할 List에 담아 List의 길이를 먼저 출력한 후 담겨진 원소를 출력하면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int A_len = Integer.parseInt(st.nextToken());
        int B_len = Integer.parseInt(st.nextToken());
        
        int[] A = new int[A_len];
        int[] B = new int[B_len];
        List<Integer> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<A_len; i++) {
            int num = Integer.parseInt(st.nextToken());
            A[i] = num;
        }

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<B_len; i++) {
            int num = Integer.parseInt(st.nextToken());
            B[i] = num;
        }

        // A, B 배열이 반드시 정렬되어 있어야 함.
        // 정렬되어 있어야 이분탐색이 가능하기 때문.
        Arrays.sort(A);
        Arrays.sort(B);

        // A 배열의 원소가 B 배열에 존재하는지 이분탐색을 진행.
        for(int i=0; i<A_len; i++) {
            if(Arrays.binarySearch(B, A[i]) < 0) {
                result.add(A[i]);
            }
        }

        sb.append(result.size() + "\n");
        for(int num : result) {
            sb.append(num + " ");
        }
        bw.write(sb.toString()+"\n");

        bw.close();
        br.close();
    }

    static boolean binarySearch(int[] arr, int n) {
        // 반복문을 통한 이분탐색 진행
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (arr[mid] < n) left = mid + 1;
            else if (arr[mid] > n) right = mid - 1;
            else return true;
        }
        return false;
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.