[해커랭크] Sparse Arrays (C++)

문제 링크: www.hackerrank.com/challenges/sparse-arrays/problem

Sparse Arrays | HackerRank

1. 주의할 점

- Strings에 특정 단어가 몇개 들어있는지 미리 기록한다

- Map을 활용하면 편하다(N: Strings 크기, M: Queries 크기 -> 시간 복잡도: MlgN)

 

2. 구현

- Strings에 들어있는 단어를 Map m에 <단어, 포함횟수> 형태로 저장한다

- Queries에 포함된 단어가 m에 몇개 들어있는지 Result 벡터에 차례대로 삽입한다

#include <bits/stdc++.h>

using namespace std;

// Complete the matchingStrings function below.
vector<int> matchingStrings(vector<string> strings, vector<string> queries) {
    map<string,int> m;
    for(int i=0;i<strings.size();i++){
        if(m.find(strings[i])==m.end())
            m[strings[i]]=1;
        else 
            m[strings[i]] +=1;
    }
    vector<int> result;
    for(int i=0;i<queries.size();i++){
        if(m.find(queries[i])==m.end())
            result.push_back(0);
        else
            result.push_back(m[queries[i]]);
    }
    return result;
}