프로그래머스 92334 - 신고 결과 받기 (Lv.1)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/92334 (2022 KAKAO BLIND RECRUITMENT)

// 프로그래머스 92334 - 신고 결과 받기 (Lv.1, 2022 KAKAO BLIND RECRUITMENT)
// https://school.programmers.co.kr/learn/courses/30/lessons/92334

// 문제 설명
// 각 유저는 다른 유저를 신고할 수 있다. report 원소는 "신고자 피신고자" 형식.
// 한 유저가 같은 유저를 여러 번 신고해도 1회로만 친다(중복 제거).
// k번 이상 신고당한 유저는 정지되고, 그 유저를 신고한 사람들에게 처리 결과 메일이 간다.
// id_list 순서대로 각 유저가 받은 메일 수를 반환하라.

// 제약 조건
// 2 <= id_list 길이 <= 1000, 1 <= report 길이 <= 200,000, 1 <= k <= 200

// 접근 — 해시맵 카운팅 O(report)
// 1) report를 set으로 중복 제거 ("신고자 피신고자" 문자열 통째로)
// 2) 피신고자별 신고당한 횟수 reportedCnt, 피신고자별 신고자 목록 reporters 수집
// 3) reportedCnt >= k 인 유저(정지 대상)를 신고한 사람마다 answer[+1]

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <sstream>
using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k)
{
    unordered_map<string, int> idx;                  // 유저 → id_list 인덱스
    for (int i = 0; i < (int)id_list.size(); i++)
        idx[id_list[i]] = i;

    unordered_set<string> seen;                      // 중복 신고 제거 ("신고자 피신고자")
    unordered_map<string, vector<string>> reporters; // 피신고자 → 신고한 사람들
    unordered_map<string, int> reportedCnt;          // 피신고자 → 신고당한 횟수

    for (const string& r : report)
    {
        if (!seen.insert(r).second) continue;        // 이미 본 신고면 건너뜀
        stringstream ss(r);
        string from, to;
        ss >> from >> to;
        reporters[to].push_back(from);
        reportedCnt[to]++;
    }

    vector<int> answer(id_list.size(), 0);
    for (const auto& p : reportedCnt)
    {
        if (p.second >= k)                           // 정지 대상
            for (const string& from : reporters[p.first])
                answer[idx[from]]++;
    }
    return answer;
}

정리

• 이 문제의 진짜 함정은 알고리즘이 아니라 “한 사람이 같은 사람을 여러 번 신고해도 1회”라는 조건이다. 중복을 제거하지 않으면 신고 횟수도 부풀고, 정지 유저를 신고한 사람에게 가는 메일 수도 부풀어 답이 둘 다 틀어진다. 그래서 "신고자 피신고자" 문자열을 통째로 unordered_set에 넣어 중복을 가장 먼저 걸러낸다.
• seen.insert(r).second는 삽입 성공 여부(bool)다. 이미 있으면 false라 if (!...) continue로 한 줄에 중복 스킵이 된다. count 후 insert 두 번 조회할 필요가 없다.
• 자료구조는 세 개로 나눴다. 피신고자 → 신고당한 횟수(정지 판정용)와 피신고자 → 신고한 사람들(메일 배달용). 정지 판정과 메일 배달은 서로 다른 방향의 조회라 둘 다 필요하다.
• id_list 순서대로 답을 채워야 하므로 유저 → 인덱스 맵을 미리 만들어 둔다. 답을 vector<int> answer(n, 0)로 잡고 신고자 인덱스에 직접 누적하면 마지막에 정렬·재배치가 필요 없다.
• 복잡도는 report를 한 번 훑고(중복 제거 + 수집), 정지 유저의 신고자만 한 번 더 도는 O(report 길이). report가 최대 20만이라 충분히 빠르다.
• 검증: 예제 1 [2,1,1,0], 예제 2 [0,0] 모두 통과(MSVC /std:c++17 /utf-8 컴파일·실행 확인).