https://school.programmers.co.kr/learn/courses/30/lessons/92334

개인적으로 "에... 이렇게까지 해야하는건가? 싶었던 문제였다. 그래서 그런지 정답률이 35%, 카카오 Lv1 문제 중 가장 어려웠다.

문제

문제에서 추출할 수 있는 정보는 다음과 같다.

• 신고자는 피신고자를 신고하며, 피신고자가 신고당한 횟수가 k 이상이면 정지된다.
• 동일한 유저에 대한 한 유저의 신고 횟수는 1회로 처리된다.
  -> (철수 영희), (철수 영희) 의 경우 영희가 신고당한 횟수는 1회만 인정된다는 뜻이다.
• 신고자가 신고한 사람이 정지당할 경우 해당 유저를 신고한 모든 사람이 메일을 받는다.
• 신고한 모든 내용을 취합하여 한꺼번에 정지시킨 뒤 메일을 발송한다.

제한사항

report 배열의 한 원소는 "신고자 피신고자"의 형태인 것을 확인할 수 있다.
즉 공백 기준으로 이 둘을 파싱하여 관련 정보를 업데이트하는 데 활용해야 한다.

입출력

동일한 신고에 대해 1회만 처리하는 것에 유의하자.

먼저 중복된 신고 시도를 막고 시작하는 것이 편할 것이기에, 신고가 문자열 형태로 들어온다는 것을 이용해 중복된 문자열을 감지할 수 있는 string-bool 형태의 map을 도입하자.

다음으로, report 배열의 공백(' ')을 감지하여 앞 뒤 문자열(사람)을 substr 함수를 통해 파싱한 뒤, 뒷사람이 신고당한 횟수를 증가시키고,
뒷사람을 신고한 사람의 명단에 앞사람을 추가해야 한다.

즉 사람 - (신고자들) 의 key-value 관계, 즉 string-vector 형태의 map을 또 도입할 수 있다.

신고한 모든 내용을 취합하여 한꺼번에 정지시킨 뒤 메일을 발송한다는 조건 충족을 위해, 모든 유저들의 신고 횟수를 담고 있는 m을 순회하며 그 value가 k개 이상이라면, 그 유저를 신고한 명단을 순회하며 명단에 있을 사람들이 받을 메일 수를 하나씩 증가시키기 위해 또다시 string-int 형태의 map인 cnt를 활용하였다.

원래 순서대로 신고자가 받는 메일 개수를 담고 반환하면 된다.

1대 다 관계를 효과적으로 활용하기 위해 map을 적극적으로 도입하였다. 물론 다양한 블로그에 다양한 풀이들이 존재하지만, 원래 알고 있던 방식들을 먼저 탄탄하게 다듬는 게 중요하다고 생각했다.

소스 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    map<string, int> m; // 특정 유저(key)가 신고당한 횟수(value)
    map<string, int> cnt;  // 특정 유저(key)가 신고 결과메일 받는 횟수(value)
    map<string, vector<string> > list; // 특정 유저(key)에 대한 신고 결과메일을 받을 사람들의 명단(value)
    map<string, bool> re; // 반복되는 신고를 막기 위해 필요
        
    for(int i=0; i<report.size(); i++){
        string str = report[i];
        if(re[str] == true){ // 같은 신고는 1회만 처리
            continue;
        } else {
            re[str] = true;
        }
        
        string tmp = "";
        for(int j=0; j<str.size(); j++){
            if(str[j] == ' '){ // 공백 기준으로 분리한다.
                tmp = str.substr(j+1); // 신고당하는 사람 추출
                m[tmp]++; // 대상의 신고 횟수 증가
                list[tmp].push_back(str.substr(0, j)); // 대상을 신고한 사람들의 명단에 추가
                break;
            }
        }
    }
    
    for(auto it: m){
        if(it.second >= k){ // 대상이 정지당하면
            for(int i=0; i<list[it.first].size(); i++){
                cnt[list[it.first][i]]++; // 이를 신고했던 사람이 받는 메일 개수 + 1
            }
        }
    }
    
    for(int i=0; i<id_list.size(); i++){
        answer.push_back(cnt[id_list[i]]); // 원래 순서대로 신고자가 받는 메일 개수를 담아 반환
    }
    return answer;
}

교훈

• map, set 등 자료구조에 대해 항상 그 필요성을 제대로 파악해야 한다.
• 풀 수 있는 문제를 빠르게 푸는 것이 중요하다.