[백준] 10816번 - 숫자 카드 2 [Java][C++]

문제 링크

---

1. 문제 풀이

$N$ 이 최대 $500,000$ 이고 각 숫자가 $-10,000,000 \sim 10,000,000$ 일 때, $M$ 개의 숫자에 대해 등장 횟수를 출력하는 문제다. 가장 간단하게는 맵을 활용해 등장 횟수를 판단할 수 있고, 주어진 숫자 카드를 정렬한 후 Lower Bound, Upper Bound 이분 탐색을 통해 등장 구간으로 등장 횟수를 구하는 방식으로 해결할 수 있다. 주어진 수의 범위가 크긴 하지만 카운팅 배열을 통해서도 해결할 수 있다.

---

2. 코드

1. 이분 탐색 [Java]

Upper Bound 의 인덱스에서 Lower Bound 의 인덱스를 빼면 해당 원소의 개수를 구할 수 있다.

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

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(upperBound(arr, num) - lowerBound(arr, num)).append(" ");
        }

        System.out.println(sb);
    }

    static int lowerBound(int[] arr, int key) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static int upperBound(int[] arr, int key) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = (left + right) / 2;

            if (arr[mid] <= key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 카운팅 배열 [Java]

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

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

public class Main {

    static final int MAX = 10_000_000;

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

        br.readLine();
        int[] cntArr = new int[MAX + 1 + MAX];
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            cntArr[Integer.parseInt(st.nextToken()) + MAX]++;
        }

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            sb.append(cntArr[Integer.parseInt(st.nextToken()) + MAX]).append(" ");
        }

        System.out.println(sb);
    }
}

3. 해시를 사용한 집합과 맵 [Java]

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;

        Map<Integer, Integer> map = new HashMap<>();

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        br.readLine();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            sb.append(map.getOrDefault(Integer.parseInt(st.nextToken()), 0)).append(" ");
        }

        System.out.println(sb);
    }
}

4. 이분 탐색 [C++]

Upper Bound 의 인덱스에서 Lower Bound 의 인덱스를 빼면 해당 원소의 개수를 구할 수 있다.

upper_bound, lower_bound 함수를 활용했다.

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

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

    int n;
    cin >> n;

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

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cout << upper_bound(v.begin(), v.end(), x) - lower_bound(v.begin(), v.end(), x) << ' ';
    }
}

5. 카운팅 배열 [C++]

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

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

constexpr int MAX = 10000000;

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

    int n;
    cin >> n;

    vector<int> cntArr(MAX + 1 + MAX);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        cntArr[x + MAX]++;
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cout << cntArr[x + MAX] << ' ';
    }
}

6. 해시를 사용한 집합과 맵 [C++]

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

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

    int n;
    cin >> n;

    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        mp[x]++;
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;

        auto it = mp.find(x);
        if (it != mp.end()) {
            cout << it->second << ' ';
        } else {
            cout << "0 ";
        }
    }
}

---

3. 풀이 정보

1. 이분 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	1384 ms	125300 KB	1534 B

2. 카운팅 배열 [Java]

언어	시간	메모리	코드 길이
Java 11	884 ms	199096 KB	795 B

3. 해시를 사용한 집합과 맵 [Java]

언어	시간	메모리	코드 길이
Java 11	1220 ms	178548 KB	818 B

4. 이분 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	292 ms	3976 KB	423 B

5. 카운팅 배열 [C++]

언어	시간	메모리	코드 길이
C++ 17	252 ms	80148 KB	455 B

6. 해시를 사용한 집합과 맵 [C++]

언어	시간	메모리	코드 길이
C++ 17	468 ms	23304 KB	520 B

---