[TIL] 2026-06-18 — 신고 결과 받기: 해시맵 카운팅과 '중복 제거' 함정
주말 백로그로 빼뒀던 프로그래머스 92334 — 신고 결과 받기(2022 KAKAO BLIND RECRUITMENT, Lv.1)를 마저 풀었다. 난이도는 낮지만 “한 사람이 같은 사람을 여러 번 신고해도 1회”라는 한 줄 조건을 놓치면 답이 통째로 틀어지는, 전형적인 “조건이 곧 함정”인 문제였다. 해시맵으로 카운팅하는 흐름과 그 함정을 정리한다.
오늘 한 일 요약
- 백로그에 있던 신고 결과 받기를 해시맵 카운팅으로 풀이 —
O(report 길이) - 중복 신고 제거를 가장 먼저 해야 하는 이유를 정리
- “정지 판정”과 “메일 배달”이 서로 다른 방향의 조회라 자료구조를 둘로 나눈 이유를 정리
- 예제 2개 모두 통과 확인 (MSVC 컴파일·실행)
문제 정리
각 유저는 다른 유저를 신고할 수 있고, report 원소는 "신고자 피신고자" 형식이다. k번 이상 신고당한 유저는 정지되고, 그 유저를 신고한 사람들에게 처리 결과 메일이 간다. id_list 순서대로 각 유저가 받은 메일 수를 반환한다.
- 단, 한 유저가 같은 유저를 여러 번 신고해도 신고 횟수는 1회로만 센다.
report길이가 최대 20만이라, 신고당 다중 루프를 돌리면 안 되고 한 번 훑는 선형 풀이가 필요하다.
핵심 함정: 중복 제거를 가장 먼저
이 문제에서 알고리즘 자체는 “센다”로 끝난다. 진짜 함정은 중복 신고다.
1
2
3
4
5
6
unordered_set<string> seen; // "신고자 피신고자" 통째로
for (const string& r : report)
{
if (!seen.insert(r).second) continue; // 이미 본 신고면 스킵
// ... 여기서부터 집계
}
만약 중복 제거를 빼먹으면 두 군데가 동시에 틀어진다.
- 신고당한 횟수가 부풀어 정지되면 안 될 유저가 정지된다 (
muzi가frodo를 3번 신고 → 3회로 세면 k=2에서 잘못 정지). - 메일 수가 부풀어 같은 신고자가 같은 정지 유저로 메일을 여러 번 받는다.
그래서 "신고자 피신고자" 문자열을 통째로 unordered_set에 넣어 중복을 맨 앞에서 걸러내는 게 정답의 전제다. seen.insert(r).second는 삽입 성공 여부(bool)라, 이미 있으면 false → if (!...) continue 한 줄로 중복 스킵이 된다. count로 확인하고 다시 insert하는 2회 조회가 필요 없다.
자료구조를 둘로 나눈 이유
“정지 판정”과 “메일 배달”은 방향이 다른 조회다. 그래서 맵을 둘로 나눴다.
1
2
unordered_map<string, int> reportedCnt; // 피신고자 → 신고당한 횟수 (정지 판정용)
unordered_map<string, vector<string>> reporters; // 피신고자 → 신고한 사람들 (메일 배달용)
reportedCnt[to]로 누가 정지되는지(>= k)를 판정하고,reporters[to]로 그 정지 유저를 누가 신고했는지 거꾸로 찾아 메일을 +1 한다.
하나의 맵으로는 두 방향을 동시에 못 풀어서, 같은 데이터를 두 형태로 들고 있는 셈이다.
id_list 순서로 답 채우기
답은 id_list 순서대로 나가야 한다. 신고자 이름으로 답 배열의 위치를 바로 찾으려면 유저 → 인덱스 맵을 미리 만들어 두면 된다.
1
2
3
4
5
6
7
8
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회”를 놓치면 정지 판정과 메일 수가 동시에 틀어진다. 중복 제거를 맨 앞에서 해야 한다.
set.insert(x).second로 중복 스킵을 한 줄에.count+insert2회 조회 대신 삽입 성공 여부 bool 하나로 처리한다.- 조회 방향이 다르면 자료구조를 나눈다. 정지 판정(피신고자→횟수)과 메일 배달(피신고자→신고자들)은 방향이 달라 맵 두 개로 들고 있는 게 깔끔하다.
- 출력 순서가 정해져 있으면 인덱스 맵으로 직접 누적. 이름→인덱스 맵을 미리 만들면 정렬·재배치 없이
id_list순서가 유지된다.