[Baekjoon Online Judge] 10815. 숫자 카드 (C++, Java)

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

핵심

N과 M이 최대 500,000이다.

 

단순 탐색으로는 N개의 원소와 M개의 원소를 각각 대응시켜 봐야 하므로 시간복잡도 O(NM)이다. (시간초과)

따라서 시간복잡도를 낮춰야 한다.

 

이분 탐색을 활용하면 M개의 각 원소에 대해 각각 O(logN)으로 탐색할 수 있다.

전체 시간복잡도는 O(MlogN)으로 줄어든다. 

 

Code (C++)

#include <algorithm>
#include <iostream>
using namespace std;
#define MAX_N 500000

int arr[MAX_N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int N, M, x;

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	sort(arr, arr + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> x;
		cout << binary_search(arr, arr + N, x) << '\n';
	}
}

 

Code (Java)

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        StringBuilder sb = new StringBuilder();
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        int M = sc.nextInt();
        int[] targets = new int[M];

        for (int i = 0; i < M; i++) {
            targets[i] = sc.nextInt();
        }

        for (int target : targets) {
            int ret = Arrays.binarySearch(arr, target);
            if (ret >= 0) {
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append(' ');
        }

        System.out.println(sb);
    }
}