[C++/프로그래머스] 신고 결과 받기

✅ LV.1

📌 2022 KAKAO BLIND RECRUITMENT

✏️ 1차 솔루션

• report("신고자 id 신고당한 id")의 문자열을 map<신고자 id, 신고당한 id> 으로 저장
• 각 id의 신고횟수를 map <이용자 id, 신고횟수> 으로 저장
• 각 id의 경고메일 횟수를 map <이용자 id, 경고메일 횟수> 으로 저장

1. 각 id에 대한 신고 횟수와 경고메일 횟수는 0으로 초기화해서 map 에 세팅
2. report 배열의 "신고자 id 신고당한 id" 는 set 에 저장해서 중복 신고 배제
3. report 배열의 문자열이 중복 신고가 아니라면 해당 문자열을 신고자 id와 신고당한 id를 분리해서 신고 당한 id의 신고횟수를 늘려주기 ➡️ map 의 값 갱신
4. 신고당한 id의 신고횟수가 k 이상이면 신고한 id와 신고당한 id에 대한 경고메일 횟수를 늘려주기 ➡️ map 의 값 갱신
5. id_list 배열의 각 id의 경고메일 횟수를 answer에 저장

📌 self feedback

• 신고횟수와 경고메일 횟수를 굳이 map 으로 관리할 필요가 없음 + 마지막에 answer 배열에 메일 값만 옮겨주는 것도 memory 낭비
• 중복 신고 배제도 set 로 한번 거쳐주는 방법이 memory 낭비일 것 같음
• 신고당한 id의 신고횟수가 k 이상인 시점의 신고자만 경고메일 횟수 늘려주면 다른 신고자들은 갱신이 되지 않는데 k 이상인 경우 발생할 때마다 다른 신고자가 존재하는지 for 문으로 찾아주기에는 memory 낭비가 심해보이나 다른 방법을 모르겠음

✏️ 2차 솔루션

1. id_list 배열의 id에 대한 인덱스와 아이디를 map<id, index> 로 저장 ➡️ map<string, int> id_idx_map

⭐️ report 배열의 "신고자 id 신고당한 id" 문자열을 map<신고당한 id, set<신고한 id>> 으로 저장
➡️ 하나의 id를 신고한 id는 여러 개이기 때문에 신고당한 id를 key로 가지는 값(신고한 id)은 set 로 저장되어야 함
➡️ map<string, set<string>> report_map

2. 신고당한 id의 신고한 id set의 size가 k 이상이면 신고자가 경고메일을 받는 경우라고 판단해 set 에 포함되어 있는 id의 id_list 인덱스 자리의 answer vector 값을 늘려주기

📌 self feedback

일단 신고횟수를 초과하면 신고자 id와 신고당한 id 모두 경고메일을 받는다고 잘못 이해
해시의 목적을 고려하여 동일한 key를 가지는 값들이 많을 때 , set를 사용하여 저장하는 방법이 관건이었음
복잡도를 줄인다고 하나의 for 문 안에 쑤셔넣는 것이 아니라 단계적으로 나눠서 계획할 필요가 있음

✏️ 2차 code

#include <string>
#include <vector>
#include <map>
#include <set>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer(id_list.size(),0);
    
    map<string, int> id_idx_map;
    map<string, set<string>> report_map;    //<신고된 id, 신고한 id>
    
    for(int i=0;i<id_list.size();i++) id_idx_map[id_list[i]]=i;

    for(int i=0;i<report.size();i++) {
        string str=report[i];
        
        string s1, s2;
        istringstream ss(str);
        ss>>s1>>s2;
        
        report_map[s2].insert(s1);
    }
    
    for(auto it:report_map) {
        if(it.second.size()>=k) {
            for(auto itt:it.second) answer[id_idx_map[itt]]++;
        }
    }
    
    return answer;
}