백준 10816 숫자 카드 2 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간 초과 오류가 발생했다.

o(n^2)이상의 복잡도는 오류가 발생해 hashmap이나 이분탐색을 사용해야 했다.

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    int arr[n];
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    int m;
    cin >> m;
    
    for(int i=0; i<m; i++){
        int target;
        cin >> target;
        
        int sum = 0;
        for(int j=0; j<n; j++)
            if(arr[j] == target)
                sum++;
        
        cout << sum << " ";
    }
    
    return 0;
}

 

 

 

1. hashmap사용 unordered_map <int, int> m; 사용

2. 이분탐색 사용 (lower_bound, upper_bound 사용)