[프로그래머스/Level 1] 신고 결과 받기

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

프로그래머스

카카오 기출 (다시 풀기, 작년 공채 때 풀었는데 왜 못풀지? ㅋ)

 

신고 내역을 담을 map과 신고 결과를 기록할 map을 각각 선언하여 문제를 해결할 수 있다.

다음과 같이 입력 값이 주어졌다고 가정해보자.

["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"], k = 2

 

신고 내역(key=신고자, value=피신고자 집합)

muzi : {"frodo", "neo"}

frodo : {"neo"} 

apeach : {"frodo", "muzi"}

neo : {}

 

신고 결과(key=피신고자, value=신고자 집합)

muzi : {"apeach"}

frodo : {"muzi", "apeach"}

apeach : {}

neo : {"muzi", "frodo"}

 

2(k)번 이상 신고를 받은 frodo와 neo가 정지되며, 해당 유저들을 신고한 muzi에게 2번, apeach 1번, frodo 1번 메일이 전송된다.

 

※ 이중 for문이 나오는 곳에서 TLE이 발생할 수 있지 않나 의심할 수 있지만, set의 최대 크기가 id_list의 크기 이므로, O(n^2) 라도 1,000 * 1,000 = 1,000,000 라서 문제없다.

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

map<string, set<string>> reportHash, resultHash;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer(id_list.size());
    for(auto r : report) {
        stringstream ss(r);
        string from, to;
        getline(ss, from, ' ');
        getline(ss, to, ' ');
        reportHash[from].insert(to);
        resultHash[to].insert(from);
    }
    
    for(int i = 0; i < id_list.size(); i++) {
        string id = id_list[i];
        for(auto report : reportHash[id]) {
            if(resultHash[report].size() >= k) answer[i]++;
        }
    }
    
    return answer;
}