<프로그래머스 C++> 신고 결과 받기 풀이

문제

유저들이 서로를 신고할 수 있고, 동일한 유저에 대한 신고는 1회로 처리된다. K번 이상 신고당한 유저는 정지되며, 해당 유저를 신고한 사람들에게 메일이 발송된다. 각 유저가 받은 메일 횟수를 return하는 문제이다.

---

문제 파악

1. 중복 신고 제거

동일한 유저에 대한 신고는 1회로 처리해야 한다.

 

이 부분은 set의 중복 제거를 이용했다.

report  = ["ryan con", "ryan con", "ryan con"]
ReportSet = {"ryan con"}  //자동으로 1개만 저장

 

2. 신고당한 횟수 계산

ReportSet을 순회하면서 피신고자의 신고 횟수를 map<string, int>에 누적한다.

 

3. 메일 횟수 계산

다시 ReportSet을 순회하면서 피신고자가 k번 이상 신고당했으면 신고자의 메일 횟수를 +1한다.

신고자의 인덱스는 map<string, int>로 미리 id_list를 저장해 빠르게 조회한다.

---

문제 풀이

#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer(id_list.size(), 0);

    set<string> ReportSet(report.begin(), report.end());

    map<string, int> ReportCount;
    map<string, int> idIndex;

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

    for(auto& r : ReportSet)
    {
        string Reported = r.substr(r.find(' ') + 1);
        ReportCount[Reported]++;
    }

    for(auto& r : ReportSet)
    {
        string Reporter = r.substr(0, r.find(' '));
        string Reported = r.substr(r.find(' ') + 1);
        if(ReportCount[Reported] >= k)
            answer[idIndex[Reporter]]++;
    }

    return answer;
}

---

코드 흐름

1. 중복 제거

set<string> ReportSet(report.begin(), report.end());

set에 report의 begin / end를 넘기면 자동으로 중복이 제거된다.

 

2. 유저 인덱스 저장

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

신고자의 answer인덱스를 O(1)로 빠르게 찾기 위해서 미리 저장한다.

 

3. 신고당한 횟수 계산

for(auto& r : ReportSet)
{
    string Reported = r.substr(r.find(' ') + 1);
    ReportCount[Reported]++;
}

"muzi frodo"의 형태로 들어오는 인자를 보면 공백 이후가 피신고자이다. 피신고자별로 신고당한 횟수를 누적한다.

 

4. 메일 횟수 계산

for(auto& r : ReportSet)
{
    string Reporter = r.substr(0, r.find(' '));
    string Reported = r.substr(r.find(' ') + 1);
    if(ReportCount[Reported] >= k)
        answer[idIndex[Reporter]]++;
}

피신고자가 k번 이상 신고당했으면 신고한 사람의 메일 횟수를 +1한다.

 

ReportSet을 두 번 순회로 분리한 이유는 한 번에 처리할 때 신고 횟수가 다 누적되기 전에 k 체크를 해버리는 경우가 있었기 때문에 두번으로 나누었다.

---

핵심 포인트

 

• set<string>으로 중복 신고를 자동 제거한다
• 신고당한 횟수 계산과 메일 횟수 계산을 두 번의 순회로 분리해야 한다