개요

신고결과받기

이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.

접근방식

1. 기본적으로 이용자의 id마다 신고를 몇번 받는지 저장을 한 후,
   각 이용자가 신고한 사람들 중 몇명이 제제를 당했는지 체크하는 방식으로 풀었다.

2. 정렬될 필요가 없으므로 unordered_map을 이용해
   이용자의 신고횟수를 저장하는 해쉬맵을 만들었다.

   	unordered_map<string, int> id_reported;

3. 그 후, 각 이용자가 신고한 사람 목록을 map안에 set을 넣어
   구현하였다.

       unordered_map<string, unordered_set<string>> reportList;

4. 그 후, report안의 문자열을 공백기준으로 조사하여
   신고자와 피신고자로 나누고 map안에 넣어줬다.

    //report에 들어온 문자열 공백 기준으로 나눠서 reportList에 넣어주기
      for (auto iter = report.begin(); iter != report.end(); ++iter) {
          string tmp = "", reporter = "";
          //각 report의 char마다
          for (char elem : *iter) {
              //공백이 나올때까지 임시 string형 변수 tmp에 더해줌 
              if (elem != ' ') tmp += elem;
              //공백이면
              else {
                  //지금 시점에서 tmp변수는 신고자이므로 reporter변수에 저장
                  reporter = tmp;
                  //tmp초기화하고 반복하면 tmp에 피신고자 저장됨
                  tmp = "";
              }
          }
          //신고자가 자신이 아니면서, 신고자 set에 피신고자가 없을때만
          if (reporter != tmp && reportList[reporter].find(tmp) == reportList[reporter].end()) {
              //신고당한 횟수 ++
              id_reported[tmp]++;
              //신고자가 key인 map의 set value에 tmp값 insert해줌
              reportList[reporter].insert(tmp);
          }
      }

   set에 넣으면 자동으로 걸러지는데
   왜 if문으로 set에 피신고자가 없을때만 동작하게 했냐면
   id_reported[tmp]++때문이다.

5. 그 후, reportList안의 각 이용자의 key에 맞는
   value값인 set을 순회하며 해당 이용자가 신고한 사람중 제제먹은 사람이
   몇명인지 저장해주었다.

   //각 이용자마다 
      for (auto Iter = id_list.begin(); Iter != id_list.end(); ++Iter) {
          //해당 이용자에 key에 맞는 set value값 순회하며 
          for (auto setIter = reportList[*Iter].begin(); setIter != reportList[*Iter].end(); setIter++) {
              //각 set의 피신고자가 제제 먹었다면
              if (id_reported[*setIter] >= k) {
                  //answer벡터 +1해줌
                  answer[Iter - id_list.begin()] ++;
              }
          }
      }
   

전체 코드

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    answer.resize(id_list.size());
    //각 이용자마다 신고당한 횟수
    unordered_map<string, int> id_reported;
    //각 이용자가 신고한 사람들(set을 통해 중복 제거)
    unordered_map<string, unordered_set<string>> reportList;

    //map에 id마다 기본적으로 0으로 초기화
    for (auto iter = id_list.begin(); iter != id_list.end(); ++iter) {
        id_reported[*iter] = 0;
    }
    //report에 들어온 문자열 공백 기준으로 나눠서 reportList에 넣어주기
    for (auto iter = report.begin(); iter != report.end(); ++iter) {
        string tmp = "", reporter = "";
        //각 report의 char마다
        for (char elem : *iter) {
            //공백이 나올때까지 임시 string형 변수 tmp에 더해줌 
            if (elem != ' ') tmp += elem;
            //공백이면
            else {
                //지금 시점에서 tmp변수는 신고자이므로 reporter변수에 저장
                reporter = tmp;
                //tmp초기화하고 반복하면 tmp에 피신고자 저장됨
                tmp = "";
            }
        }
        //신고자가 자신이 아니면서, 신고자 set에 피신고자가 없을때만
        if (reporter != tmp && reportList[reporter].find(tmp) == reportList[reporter].end()) {
            //신고당한 횟수 ++
            id_reported[tmp]++;
            //신고자가 key인 map의 set value에 tmp값 insert해줌
            reportList[reporter].insert(tmp);
        }
    }
        //각 이용자마다 
        for (auto Iter = id_list.begin(); Iter != id_list.end(); ++Iter) {
            //해당 이용자에 key에 맞는 set value값 순회하며 
            for (auto setIter = reportList[*Iter].begin(); setIter != reportList[*Iter].end(); setIter++) {
                //각 set의 피신고자가 제제 먹었다면
                if (id_reported[*setIter] >= k) {
                    //answer벡터 +1해줌
                    answer[Iter - id_list.begin()] ++;
                }
            }
        }

    return answer;
}

문풀후생

set으로 중복체크가 아닌 map<string, string>에서
value값에 피신고자를 string.find() 함수를 사용하여 중복을 체크하고
중복이 아니라면 +=을 이용해 더해주는 방식도 생각했었다.

//string a,b일때,
if(m[b].find(a)==string::npos)

하지만 이렇게 중복검사를 하자 테케를 통과하지 못해서 조사를 했었다.

map이랑 string이랑 find가 겹치는 문제인가 싶어서
문서들을 들여다보고 조사한 결과, 반례를 떠올릴 수 있었다.

처음 map에 피신고자로 들어간 string변수와
겹치는 string변수가 그다음에 들어간다면 find에서 이미 있다고 판단해서 거른다.

ex)
id_list=["muzi", "muzisung", "apeach", "neo"]
report=["frodo muzisung", "frodo muzi", "apeach neo", "muzi neo"]

이런식일때

1. frodo가 muzisung을 신고했다. map에 저장해준다.
   m["frodo"] ="muzisung"+" "
   (공백으로 분리해 sstream을 이용해 마지막에 구별하는 방식이다.)

2. frodo가 muzi를 신고했을 때,
   m["frodo"].find("muzi")에서 muzi를 발견하는 상황이므로
   muzi가 저장이 되지않는다.