[BaekJoon] #10815 - 숫자 카드 [Java][C++]

문제 링크

---

1. 아이디어

$N$이 최대 $500{,}000$이고 각 숫자가 $-10{,}000{,}000$ ~ $10{,}000{,}000$일 때, $M$개의 숫자에 대해 등장한 적이 있는지 여부를 출력하는 문제다. 가장 간단하게는 집합을 활용해 등장 여부를 판단할 수 있고, 주어진 숫자 카드를 정렬한 후 이분 탐색을 통해 등장했는지 판단하는 방식으로 해결할 수 있다. 주어진 수의 범위가 크긴 하지만 인덱스와 숫자를 매핑한 방문 체크 배열을 통해서도 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
이분 탐색	$O((N + M) \log N)$	$O(N)$
방문 체크	$O(N + M)$	$O(K)$
해시셋	$O(N + M)$	$O(N)$

($N$ = 입력값 n, $M$ = 입력값 m, $K$ = 값의 범위 $2 \times 10^7 + 1$)

---

3. 코드

풀이 1: 이분 탐색 [Java][C++]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (m-- > 0) {
            int x = Integer.parseInt(st.nextToken());

            if (Arrays.binarySearch(arr, x) >= 0) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb);
    }
}

Arrays.binarySearch 메서드를 활용했고 주어진 배열에 존재하지 않으면 음수를 반환하는 것을 활용했다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;
    sort(v.begin(), v.end());

    int m;
    cin >> m;

    while (m--) {
        int x;
        cin >> x;
        cout << binary_search(v.begin(), v.end(), x) << ' ';
    }
}

찾으면 true, 못 찾으면 false를 반환하는 std::binary_search 함수를 활용했다.

---

풀이 2: 방문 체크 [Java][C++]

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

public class Main {

    static final int MAX = 10_000_000;
    static boolean[] seen = new boolean[MAX + 1 + MAX];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;


        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (n-- > 0) {
            int x = Integer.parseInt(st.nextToken());
            seen[x + MAX] = true;
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (m-- > 0) {
            int x = Integer.parseInt(st.nextToken());

            if (seen[x + MAX]) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb);
    }
}

음수 범위도 커버해야 해서 앞에 음수 범위만큼의 패딩을 주어 $-10{,}000{,}000$이 인덱스 0에 매핑되도록 했다.

#include <bits/stdc++.h>
using namespace std;

const int MAX = 10'000'000;
bool seen[MAX + 1 + MAX];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;
        seen[x + MAX] = true;
    }

    int m;
    cin >> m;

    while (m--) {
        int x;
        cin >> x;
        cout << seen[x + MAX] << ' ';
    }
}

음수 범위도 커버해야 해서 앞에 음수 범위만큼의 패딩을 주어 $-10{,}000{,}000$이 인덱스 0에 매핑되도록 했다.

---

풀이 3: 해시셋 [Java][C++]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        Set<Integer> set = new HashSet<>();

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (n-- > 0) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (m-- > 0) {
            int x = Integer.parseInt(st.nextToken());

            if (set.contains(x)) {
                sb.append("1 ");
            } else {
                sb.append("0 ");
            }
        }

        System.out.println(sb);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    unordered_set<int> st;

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;
        st.insert(x);
    }

    int m;
    cin >> m;

    while (m--) {
        int x;
        cin >> x;
        cout << st.count(x) << ' ';
    }
}

---