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

[24] 신고 결과 받기

책 구매하기

문제 정보

• 분류: 해시
• 정답률: 36%
• 권장 시간 복잡도: O(U + R)
• 핵심 키워드: 중복 신고 제거, 집합, 해시, 메일 카운트
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/92334

문제를 읽을 때 체크할 포인트

신고를 한 번만 인정한다는 조건 때문에 먼저 중복 신고를 지우는 게 우선이다. 이후에는 각 유저가 몇 번 신고당했는지 세고, 정지된 유저를 신고한 사람만 메일 수를 올리면 된다.

배열을 처음부터 끝까지 비교하는 쪽으로 가면 코드는 길어지고 예외도 많아진다. 이 문제는 필요한 정보를 키-값으로 압축하는 순간 풀이가 짧아진다.

풀이 흐름

1. report를 set으로 바꿔 중복 신고를 제거한다.
2. 신고당한 횟수를 카운트한다.
3. 정지 기준 이상인 유저를 신고한 사람의 메일 수를 1씩 증가시킨다.

구현할 때 놓치기 쉬운 부분

같은 사람이 같은 사람을 여러 번 신고해도 한 번만 인정된다. 그래서 신고 기록을 바로 세기 전에 중복 신고를 먼저 제거해야 한다. 이 단계를 빼먹으면 메일 발송 수가 실제보다 커진다.

파이썬 정답 코드

def solution(id_list, report, k):
  # report를 set으로 바꿔 중복 신고를 제거한다.
  unique_reports = set(report)
  reported_count = {user: 0 for user in id_list}
  reported_by = {user: [] for user in id_list}

  # 신고당한 횟수를 카운트한다.
  for item in unique_reports:
    reporter, reported = item.split()
    reported_count[reported] += 1
    reported_by[reported].append(reporter)

  mail_count = {user: 0 for user in id_list}
  # 정지 기준 이상인 유저를 신고한 사람의 메일 수를 1씩 증가시킨다.
  for user in id_list:
    if reported_count[user] >= k:
      for reporter in reported_by[user]:
        mail_count[reporter] += 1

  return [mail_count[user] for user in id_list]

시간 복잡도

U는 id_list의 길이, R은 중복 제거 후 report의 길이이다.

사용자별 집합과 카운터를 준비하는 데 U가 들고, 신고 목록을 중복 제거하고 집계하는 데 R이 든다. 둘 중 하나가 다른 하나에 중첩되지 않으므로 합으로 정리한다.

따라서 시간 복잡도는 O(U + R)이다.