신고 결과 받기

문제 보기 · Level 1 · 2022 KAKAO BLIND RECRUITMENT · 정답률 43% · 푼 사람 41,951명 (2026-09-30 기준)¹

문제

“신고자 피신고자” 꼴의 신고 기록이 주어진다. 같은 사람을 여러 번 신고해도 한 번으로 센다. k번 이상 신고당한 사람은 정지되고, 그를 신고한 사람마다 메일이 한 통씩 간다. id_list 순서대로 각 사람이 받은 메일 수를 돌려준다.

사용자 2~1,000명
신고 기록 최대 200,000개
1 ≤ k ≤ 200

풀이

막히면 한 단계씩 펼친다.

필요한 개념

딕셔너리와 집합: 겹치는 신고 없애기(집합), 사람별로 “나를 신고한 사람들” 모으기(딕셔너리 안의 집합).
집합: 신고 기록은 (신고자, 피신고자) 순서쌍의 집합이다. 집합은 같은 원소를 한 번만 담으니 겹친 신고가 저절로 하나가 된다. 순서쌍이라 a → b와 b → a는 다른 신고로 남는다.

1단계 · 작은 예로 손으로 풀기

사용자 [a, b, c], 신고 [“a b”, “a b”, “c b”, “b a”], k = 2

겹친 신고를 하나로: a→b, c→b, b→a
사람별로 나를 신고한 사람: b ← {a, c}, a ← {b}, c ← {}
2명 이상에게 신고당한 b만 정지
b를 신고한 a와 c가 메일을 한 통씩 받는다
id_list 순서대로 [a 1, b 0, c 1] → [1, 0, 1]

2단계 · 가장 단순한 방법과 그 속도

사람마다 신고 기록 20만 개를 다 훑어 “나를 신고한 사람”을 찾으면 1,000 × 200,000 = 2억 번이다. 파이썬에서 20초쯤 걸려 안 된다. 게다가 같은 신고를 여러 번 세지 않게 따로 처리해야 한다.

3단계 · 핵심 아이디어

기록을 한 번만 훑으며 필요한 것을 표에 모은다.

겹친 신고 없애기: set(report)로 같은 문자열을 하나로 만든다.
사람별로 모으기: 딕셔너리 reporters에 “피신고자 → 나를 신고한 사람들의 집합”을 적는다. 집합이라 같은 사람이 두 번 들어가지 않는다.
정지와 메일: 집합의 크기가 k 이상이면 정지다. 그 집합의 사람마다 메일 수를 1씩 늘린다.
그래프로 보면: 겹친 신고를 없앤 뒤 신고를 화살표 a → b로 그리면, reporters[b]의 크기는 b로 들어오는 화살표 수(진입 차수)다. 정지는 “진입 차수가 k 이상”이다(그래프의 기초).

떠올리는 신호: “같은 것은 한 번만”, “사람별로” → 집합과 딕셔너리.

4단계 · 코드 흐름

사용자마다 빈 집합을 가진 딕셔너리 reporters를 만든다.
겹침을 없앤 신고마다 “a b”를 a, b로 나눠 reporters[b]에 a를 넣는다.
사용자마다 0인 메일 수 딕셔너리 mail을 만든다.
reporters의 집합 크기가 k 이상인 사람에 대해, 그 집합의 사람마다 mail을 1 늘린다.
id_list 순서대로 mail 값을 리스트로 돌려준다.

5단계 · 파이썬 코드

def solution(id_list, report, k):
    reporters = {name: set() for name in id_list}   # 피신고자 → 신고한 사람들
    for r in set(report):                           # 같은 신고는 한 번만
        a, b = r.split()                            # "a b" → a="a", b="b"
        reporters[b].add(a)

    mail = {name: 0 for name in id_list}
    for b, who in reporters.items():
        if len(who) >= k:                           # 정지된 사람
            for a in who:
                mail[a] += 1
    return [mail[name] for name in id_list]

{name: set() for name in id_list}: 사람마다 빈 집합을 만든다. 사람마다 따로 만들어야 한다.
a, b = r.split(): 빈칸으로 나눈 두 조각을 두 이름에 담는다.
[mail[name] for name in id_list]: id_list 순서대로 메일 수를 모은다.

6단계 · 실행 추적

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

겹침을 없앤 신고: muzi→frodo, apeach→frodo, frodo→neo, muzi→neo, apeach→muzi

피신고자	신고한 사람들	정지?
muzi	{apeach}	아니오
frodo	{muzi, apeach}	예
apeach	{}	아니오
neo	{frodo, muzi}	예

메일: frodo 정지로 muzi, apeach +1, neo 정지로 frodo, muzi +1 → [muzi 2, frodo 1, apeach 1, neo 0]

7단계 · 복잡도와 흔한 실수

신고 R개를 한 번, 사용자 N명을 한 번 훑으니 평균 \(O(R + N)\)이다.

같은 사람이 같은 사람을 여러 번 신고한 것을 여러 번 세면 틀린다.
답은 id_list 순서여야 한다. 딕셔너리를 그대로 돌려주면 안 된다.
dict.fromkeys(id_list, set())로 집합을 만들면 모든 사람이 같은 집합 하나를 나눠 쓰게 되어 틀린다. 컴프리헨션으로 사람마다 새로 만든다.

검증: 문제의 예시 2개를 통과했고, 무작위 입력 1,000개에서 모든 (신고자, 피신고자) 쌍을 직접 세는 느린 풀이와 결과가 같았다 — 04_pg92334_p1.py

프로그래머스 스쿨, “신고 결과 받기” (https://school.programmers.co.kr/learn/courses/30/lessons/92334), 2026-09-30 조회. ↩