프로그래머스 신고 결과 받기 해시맵 풀이

지문에 한 줄로 스쳐 지나가는 조건이 답을 통째로 뒤집는 문제가 있다. “한 사람이 같은 사람을 여러 번 신고해도 1회로 처리한다” — 이 한 줄을 어디서 처리하느냐로 정답과 오답이 갈린다. 이 글에서는 그 함정을 먼저 짚고, 해시맵을 두 개로 나눠 카운팅하는 구현을 이야기하려 한다.

문제 정리

각 유저는 다른 유저를 신고할 수 있고, report 원소는 "신고자 피신고자" 형식이다. k번 이상 신고당한 유저는 정지되고, 그 유저를 신고한 사람들에게 처리 결과 메일이 간다. id_list 순서대로 각 유저가 받은 메일 수를 반환한다.

• 단, 한 유저가 같은 유저를 여러 번 신고해도 신고 횟수는 1회로만 센다.
• report 길이가 최대 20만이라, 신고당 다중 루프를 돌리면 안 되고 한 번 훑는 선형 풀이가 필요하다.

트러블슈팅 — 중복 제거를 가장 먼저 해야 하는 이유

이 문제에서 알고리즘 자체는 “센다”로 끝난다. 진짜 함정은 중복 신고다.

unordered_set<string> seen;   // "신고자 피신고자" 통째로
for (const string& r : report)
{
    if (!seen.insert(r).second) continue;   // 이미 본 신고면 스킵
    // ... 여기서부터 집계
}

만약 중복 제거를 빼먹으면 두 군데가 동시에 틀어진다.

1. 신고당한 횟수가 부풀어 정지되면 안 될 유저가 정지된다 (muzi가 frodo를 3번 신고 → 3회로 세면 k=2에서 잘못 정지).
2. 메일 수가 부풀어 같은 신고자가 같은 정지 유저로 메일을 여러 번 받는다.

그래서 "신고자 피신고자" 문자열을 통째로 unordered_set에 넣어 중복을 맨 앞에서 걸러내는 게 정답의 전제다. seen.insert(r).second는 삽입 성공 여부(bool)라, 이미 있으면 false → if (!...) continue 한 줄로 중복 스킵이 된다. count로 확인하고 다시 insert하는 2회 조회가 필요 없다.

기술 구현 — 자료구조를 둘로 나눈 이유

“정지 판정”과 “메일 배달”은 방향이 다른 조회다. 그래서 맵을 둘로 나눴다.

unordered_map<string, int>            reportedCnt;  // 피신고자 → 신고당한 횟수 (정지 판정용)
unordered_map<string, vector<string>> reporters;    // 피신고자 → 신고한 사람들 (메일 배달용)

• reportedCnt[to]로 누가 정지되는지(>= k)를 판정하고,
• reporters[to]로 그 정지 유저를 누가 신고했는지 거꾸로 찾아 메일을 +1 한다.

하나의 맵으로는 두 방향을 동시에 못 풀어서, 같은 데이터를 두 형태로 들고 있는 셈이다.

id_list 순서로 답 채우기

답은 id_list 순서대로 나가야 한다. 신고자 이름으로 답 배열의 위치를 바로 찾으려면 유저 → 인덱스 맵을 미리 만들어 두면 된다.

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

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]]++;            // 신고자 인덱스에 직접 누적

answer를 0으로 채워 두고 신고자 인덱스에 직접 ++ 하므로, 마지막에 정렬하거나 재배치할 필요가 없다.

복잡도와 검증

• report를 한 번 훑어 중복 제거 + 집계, 그 뒤 정지 유저의 신고자만 한 번 더 도므로 O(report 길이). report 최대 20만에 충분히 빠르다.
• 공간은 맵 세 개로 O(유저 수 + report 길이).

입력	기대	결과
예제 1 (muzi/frodo/apeach/neo, k=2)	[2,1,1,0]	✅
예제 2 (con/ryan, 같은 신고 4번, k=3)	[0,0]	✅

예제 2가 함정 검증용이다. "ryan con"이 4번 들어와도 중복 제거로 1회 → con은 1회 신고당함 → k=3 미만이라 정지 없음 → [0,0]. 중복 제거를 빼먹었다면 4회로 세어 con이 정지되고 ryan이 메일을 받아 [1,0]이 나왔을 것이다.

정리 — 이 문제에서 남은 것

1. 쉬운 문제일수록 조건 한 줄이 함정이다. “여러 번 신고해도 1회”를 놓치면 정지 판정과 메일 수가 동시에 틀어진다. 중복 제거를 맨 앞에서 해야 한다.
2. set.insert(x).second로 중복 스킵을 한 줄에. count + insert 2회 조회 대신 삽입 성공 여부 bool 하나로 처리한다.
3. 조회 방향이 다르면 자료구조를 나눈다. 정지 판정(피신고자→횟수)과 메일 배달(피신고자→신고자들)은 방향이 달라 맵 두 개로 들고 있는 게 깔끔하다.
4. 출력 순서가 정해져 있으면 인덱스 맵으로 직접 누적. 이름→인덱스 맵을 미리 만들면 정렬·재배치 없이 id_list 순서가 유지된다.

핵심 요약 — “같은 사람을 여러 번 신고해도 1회” 조건 때문에 중복 제거가 모든 집계의 전제다. 그리고 정지 판정(피신고자→횟수)과 메일 배달(피신고자→신고자들)은 조회 방향이 달라서 맵을 둘로 나누는 게 깔끔하다.