[백준 | 10815] 숫자 카드 - Java

📃 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


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

        int N = Integer.parseInt(br.readLine());
        int[] cards = new int[N];
        String[] inputNum1 = br.readLine().split(" ");
        for (int i = 0; i < inputNum1.length; i++) {
            cards[i] = Integer.parseInt(inputNum1[i]);
        }

        Arrays.sort(cards);

        int M = Integer.parseInt(br.readLine());
        int[] compareCards = new int[M];
        String[] inputNum2 = br.readLine().split(" ");
        for (int i = 0; i < inputNum2.length; i++) {
            compareCards[i] = Integer.parseInt(inputNum2[i]);
        }

        for (int i = 0; i < compareCards.length; i++) {
            bw.write(binarySearch(cards, compareCards[i]) + " ");
        }

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

    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return 1;
            }

            if (arr[mid] < target) {
                low = mid + 1;
            }

            if (arr[mid] > target) {
                high = mid - 1;
            }
        }
        return 0;
    }
}

✏ 풀이

시간 제한 : 2초
N(1 ≤ N ≤ 500,000)
M(1 ≤ M ≤ 500,000)

상근이의 카드를 직접 비교하는 방법은 $O(n * M)$ 의 시간 복잡도를 가지므로 시간 초과가 발생할 수 있습니다. 따라서 이진 탐색 알고리즘을 사용하였습니다. 이진 탐색을 사용하기 위해서는 우선 배열을 정렬해야 하며, 자바의 Arrays.sort() 메서드를 사용하여 카드를 정렬하였습니다.

 

이후 정렬된 카드 리스트에 대해 비교 카드를 이진 탐색을 통해 확인하였습니다.

모든 비교 카드에 대해 이진 탐색을 수행하면 전체 시간 복잡도는 $O(M log N)$ 이 됩니다. 정렬 알고리즘과 이진 탐색을 포함한 이 코드의 전체 시간 복잡도는 $𝑂((𝑁+𝑀)log⁡𝑁)O((N+M)logN)$ 입니다.