백준 10816 (숫자 카드 2) / C++

문제 링크 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

> 풀이

1. 첫 번째 풀이 : 이진 탐색을 활용하여 upper_bound와 lower_bound 값을 구하자 ==> 시간 초과

 

2. 두 번째 풀이 : <algorithm>에서 제공하는 upper_bound와 lower_bound를 써보자 ==> 시간 초과

 

==> 시간 복잡도가 O(N * log N) 일 텐데..? 안 되는 이유 알려주시면 감사하겠습니다..

 

3. 세 번째 풀이 : 인터넷을 통해 열심히 찾아보니까 해시 맵 (unordered_map)을 사용하면 O(1)에 가까운 시간 복잡도로 탐색할 수 있더라고요.. 한 번도 써본 적이 없어서 https://en.cppreference.com/w/cpp/container/unordered_map참고하여 코드 작성했습니다. 공부가 많이 부족하네요..

 

<1, 2번 풀이 (시간 초과)>

#include <cstdio>
#include <algorithm>

using namespace std;

int arrN[100001];
int arrM[100001];

int main() {
    int M, N;
    int count = 0;

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arrN[i]);

    scanf("%d", &M);
    for (int i = 0; i < M; i++)
        scanf("%d", &arrM[i]);

    sort(arrN, arrN + N);

    for (int i = 0; i < M; i++)
        printf("%d ", upper_bound(arrN, arrN + N, arrM[i]) - lower_bound(arrN, arrN + N, arrM[i]));

    return 0;
}

 

<3번 풀이>

#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main() {
    int N, M;
    int num;
    unordered_map <int, int> umap;
    
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &num);
        umap[num]++;
    }
    
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        scanf("%d", &num);
        printf("%d ", umap[num]);
    }
    
    return 0;
}

(개발환경 : vs code로 바꿨어요 ㅎㅎ)