[Programmers] Risultati delle segnalazioni

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

Ripasso C++

unordered_map<T, T>
- Stesso utilizzo di map
- map esegue l’ordinamento su insert/erase; unordered_map no, quindi è più veloce.
- Ricerca in map: O(log n)
- unordered_map: O(1), caso peggiore O(n)
- ref: Blog1, Blog2
stringstream
- str(): estrae dati del tipo appropriato dal buffer, escludendo spazi e ‘\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; // si possono usare puntatori
6

7
  for (const auto& it: v)
8
    // se il costo della copia è alto, usare const pointer

Soluzione

Mappare ogni utente a un indice per poterlo identificare.
Costruire una mappa “chiave: utente segnalato, valore: insieme degli utenti che lo hanno segnalato”.
Usando le informazioni del punto 2, se k o più persone hanno segnalato qualcuno, aggiornare le informazioni sull’utente bannato in base agli indici del punto 1.

Codice

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; // assegnare un indice a ogni utente
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; // memorizzare l'insieme dei segnalatori per utente segnalato
16
    stringstream ss;
17

18
    for (auto rep: report) {
19
        ss.str(rep);
20
        string first, second;
21
        ss >> first >> second; // separare per spazio usando l'output di stringstream
22

23
        report_map[second].insert(first); // memorizzare first (il segnalatore) nell'insieme di second
24
        ss.clear();
25
    }
26

27
    for (auto it: report_map) {
28
        if (it.second.size() >= k) { // per gli utenti segnalati da k o più persone
29
            for (auto set_it: it.second) { // trovare ogni segnalatore tramite indice e notificarlo
30
                int idx = idx_map[set_it];
31
                answer[idx]++;
32
            }
33
        }
34
    }
35
    return answer;
36
}