【白俊】10816番カード2

1969 ワード
白駿 テキストリンク

【白俊】10816番カード2


質問リンク:https://www.acmicpc.net/problem/10816

問題とI/O



質問へのアクセス


最初はバイナリ探索を考え、ハッシュの使い方も考えました.ハッシュ関数を用いるとO(1)の時間内に値を見つけることができるのでhash mapを用いて実現する.
まず入力を受信し,ターゲット数をハッシュテーブルに格納し,ルートにハッシュテーブルの値があるか否かを判断し,ない場合はスキップしてkeyにvalue+1を行う.
最終時間複雑度はO(N)であるべきである.ハッシュテーブルでの検索に要する時間はO(1)であるが,N個の値を検索しなければならないからである.

コード実装

#include <iostream>
#include <unordered_map>

using namespace std;
int target[500001];
int sanggeon[500001];
int targetNum, haveNum;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    unordered_map<int, int> hashMap;

    cin >> haveNum;
    for(int i = 0 ; i < haveNum ; i++){
        cin >> sanggeon[i] ;
    }
    cin >> targetNum;
    for(int i = 0 ; i < targetNum ; i++){
        cin >> target[i];
        hashMap[target[i]] = 0;
    }
    for(int i = 0 ; i < haveNum ; i++){
        auto it = hashMap.find(sanggeon[i]);
        if(it != hashMap.end()){
            it->second = it->second + 1;
        }
    }
    for(int i = 0 ; i < targetNum ; i++){
        auto it = hashMap.find(target[i]);
        cout << it->second << " ";
    }
    
}

評価


久しぶりにアルゴリズムの問題をして、とても面白くて、、、ほほほ
ChartType属性の説明ヘルプ(VBA)
混同反応を用いた概念2-state hook(TIL#02)