Level 1. 신고 결과 받기

Level 1. 신고 결과 받기

 

 

(내가 신고한 사람, 나를 신고한 사람, 정지 여부)를 저장하는 사용자 정점으로 구성된 방향 그래프를 만들어 해결했다.

• 내가 신고한 사람을 나가는 간선, 나를 신고한 사람을 들어오는 간선으로 간주했다.

 

중복을 허용하지 않도록 unordered_set을 사용했고 인접 리스트 방식이라고 할 수 있다.

 

그래프를 구성하면서 신고 횟수가 k번이 넘었는지 확인하고, 마지막에 내가 신고한 사람 중 bSuspended가 true인 개수를 세어 해결했다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct user
{
    unordered_set<user*> reports;
    unordered_set<user*> reported;
    bool bSuspended;
};

pair<string, string> split(string report)
{
    size_t blank_pos = report.find(' ');

    return {report.substr(0, blank_pos), report.substr(blank_pos + 1)};
}

vector<int> solution(vector<string> id_list, vector<string> report, int k)
{
    size_t size = id_list.size();
    vector<int> answer(size);
    unordered_map<string, user> users;

    for (string id : id_list)
        users[id] = user{unordered_set<user*>(), unordered_set<user*>(), false};

    for (string rpt : report)
    {
        pair<string, string> pr = split(rpt);

        users[pr.first].reports.emplace(&users[pr.second]);
        users[pr.second].reported.emplace(&users[pr.first]);

        if (k <= users[pr.second].reported.size())
            users[pr.second].bSuspended = true;
    }

    for (int i = 0; i < size; ++i)
    {
        unordered_set<user*> reports = users[id_list[i]].reports;

        answer[i] = count_if(reports.begin(), reports.end(), [](user* u) { return u->bSuspended; });
    }

    return answer;
}

 

다른 사람의 풀이인데 꽤 신박하다.

 

report의 "신고자 피신고자" 문자열을 쪼개지 않고 그 자체로 중복을 제거했다.

 

또 그래프 등을 만들어 각 신고자별로 답을 구하는 대신, 신고 당한 횟수를 미리 계산하고 중복이 제거된 신고 정보를 순회하며 내가 신고한 사람이 k번 이상 신고 당했는지 확인했다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <unordered_map>
#include <sstream>

using namespace std;

pair<string, string> split(string report)
{
    istringstream iss(report);
    string reporter, reportee;

    iss >> reporter >> reportee;

    return {reporter, reportee};
}

vector<int> solution(vector<string> id_list, vector<string> report, int k)
{
    size_t size = id_list.size();
    vector<int> answer(size);
    unordered_set<string> report_unique;
    unordered_map<string, unsigned> user_id, report_count;

    for (int i = 0; i < size; ++i)
        user_id[id_list[i]] = i;

    for (string& rpt : report)
    {
        if (report_unique.find(rpt) == report_unique.end())
        {
            pair<string, string> info = split(rpt);

            report_unique.emplace(rpt);
            ++report_count[info.second];
        }
    }

    for (string rpt : report_unique)
    {
        pair<string, string> info = split(rpt);

        if (k <= report_count[info.second])
            ++answer[user_id[info.first]];
    }

    return answer;
}