[Programmers] Get Report Results

https://programmers.co.kr/learn/courses/30/lessons/92334?language=cpp ref: https://wadekang.tistory.com/6

C++ refresher

unordered_map<T, T>
- Same usage as map
- map triggers sorting on insert/erase; unordered_map does not, so it’s faster.
- map lookup: O(log n)
- unordered_map: O(1), worst case O(n)
- ref: Blog1, Blog2
stringstream
- str(): extracts data of the appropriate type from the buffer, excluding spaces and ‘\n’
- ref: Blog1, HowToUse
Ranged-based for loops, auto
- ref: Auto type inference, Ranged-based for

1
  for (auto it: v)
2
  cout << it;
3

4
  for (auto& it: v)
5
    it *= 2; // can use pointers
6

7
  for (const auto& it: v)
8
    // if copy cost is high, use const pointer

Solution

Map each user to an index so they can be identified.
Build a mapping of “key: reported user, value: set of users who reported them”.
Using the info from step 2, if k or more people reported someone, update the banned user info based on the indices from step 1.

Code

1
#include <string>
2
#include <vector>
3
#include <unordered_map>
4
#include <set>
5
#include <sstream>
6

7
using namespace std;
8

9
vector<int> solution(vector<string> id_list, vector<string> report, int k) {
10
    vector<int> answer(id_list.size(), 0);
11
    unordered_map<string, int> idx_map; // assign index to each user
12
    for (int i = 0; i < id_list.size(); i++)
13
        idx_map[id_list[i]] = i;
14

15
    unordered_map<string, set<string>> report_map; // store the set of reporters per reported user
16
    stringstream ss;
17

18
    for (auto rep: report) {
19
        ss.str(rep);
20
        string first, second;
21
        ss >> first >> second; // split by space using stringstream output
22

23
        report_map[second].insert(first); // store first (the reporter) in second's set
24
        ss.clear();
25
    }
26

27
    for (auto it: report_map) {
28
        if (it.second.size() >= k) { // for users reported by k or more people
29
            for (auto set_it: it.second) { // find each reporter by index and notify them
30
                int idx = idx_map[set_it];
31
                answer[idx]++;
32
            }
33
        }
34
    }
35
    return answer;
36
}