[c++] 백준 10816 - 숫자 카드 2(이분 탐색, 데이터 정리, unordered_map, 나중에 다시)

0. [c++] 백준

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

숫자 카드 2 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	11172	3382	2352	33.677%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 

3 0 0 1 2 0 0 2

1. 풀이

이번 문제는 이분 탐색을 하라는 문제지만 기본적인 이분 탐색만을 활용하면 시간 초과가 발생하여서 다른 방법을 찾아보았다.

원래 기본적인 이분 탐색을 하여 이 문제를 해결하면 시간 복잡도는 O(M*lnN)에 해당하는 시간이 걸리게 되어 대략 1천만으로 충분히 해결될 시간이라 예상을 하는데, 입출력을 printf, scanf로 바꾸어도 시간 초과를 하여서 다른 방법을 구상해보았다.

아래에 나온 방법은 입력을 받은 이후, 그 데이터를 새로이 분류하는 방식의 알고리즘이다.

1. 주어진 입력을 algorithm의 sort 함수를 활용하여 정렬을 해주었다.

2.  for문을 통해 정렬한 함수를 순회하며 vector<pair<int, int> >에 쌍을 지어 first는 등장한 숫자, second는 숫자가 등장한 횟수를 담아주었다.

3. 이렇게 정렬한 vector에서 이분 탐색을 시행하였다.

이렇게 하는 경우의 시간 복잡도를 살펴보자.

1번 시행을 하는데, 이때 시간 복잡도는 quick sort의 시간복잡도의 일반적인 경우 n*logn이 걸리고 최악의 경우 n^2가 소요된다.

2번 시행의 시간 복잡도는 N

3번 시행의 시간 복잡도는 ln(벡터의 크기)가 소요되게 된다. 간단히 최악의 경우 ln(N)이 소요된다.

즉, 최악의 경우 n^2 + N + ln(N) 으로 O(N) = n^2 이 된다.

이때, n은 최대 500,000의 입력으로 잉??? (500,000)^2은 250,000,000,000으로 시간 초과가 하지 않나??

음으으으으으 나중에 다시 확인해보자.

---------------------------------------------------------

unordered_map을 활용해서 푸는 방법도 존재하였다.

이는 해시를 이용한 방법이라고 하는데, 이는 조금 더 공부를 해야 알 것 같다.

시간 복잡도는 최악의 경우에 O(N)인 방법이라 한다.

2. 소스코드

#include<cstdio>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M, ret;
int arr[500010];
 
int main() {
    scanf("%d", &N);
 
    for (int i = 0;i<N;i++) {
        scanf("%d", &arr[i]);
    }
 
    sort(arr, arr + N);
    vector<pair<int, int>> sum;
 
    sum.push_back({ arr[0],1 });
    for (int i = 1;i < N;i++) {
        if (arr[i] == sum.back().first)
            sum.back().second++;
        else
            sum.push_back({ arr[i], 1 });
    }
 
    scanf("%d", &M);
    int temp;
 
    for (int i = 0; i < M; i++) {
        scanf("%d", &temp);
        ret = 0;
        int left = 0, right = sum.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sum[mid].first > temp) {
                right = mid - 1;
            }
            else if (sum[mid].first < temp) {
                left = mid + 1;
            }
            else {
                ret = sum[mid].second;
                break;
            }
        }
        printf("%d ", ret);
    }
}

----------------------------------------------------------------------------------------

unordered_map 활용

#include <stdio.h>
#include <algorithm>
#include <unordered_map>
 
using namespace std;
 
int n, m, a, b;
unordered_map <int, int> mmap;
 
bool compare(int a, int b) {
    return a < b;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        mmap[a]++;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &b);
        printf("%d ", mmap[b]);
    }
}

3. 참고

https://modoocode.com/224

http://www.cplusplus.com/reference/unordered_map/unordered_map/

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!