파이썬, 자바스크립트_카카오 Lv.1 - 신고 결과 받기

ref: https://programmers.co.kr/learn/courses/30/lessons/92334

문제 요약

각 유저는 한 번에 한 명의 유저를 신고
신고 횟수에 제한은 없습니다
동일한 유저에 대한 신고 횟수는 1회로 처리
k번 이상 신고된 유저는 게시판 이용이 정지
해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송
모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지, 정지메일 보냄.
id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수

제한:

2 ≤ id_list의 길이 ≤ 1,000
1 ≤ report의 길이 ≤ 200,000
전부 알파벳 소문자
1 ≤ k ≤ 200, k는 자연수

풀기 전 생각:

해시 테이블 관련 문제로 보인다.
신고 받은 사람을 키 값으로 두고,
report를 돌면서 신고한 사람을 리스트에 넣는다면, 시간복잡도는 O(1).
report의 길이가 200,000이기 때문에 1초에 2000만번 연산을 하는 파이썬에겐 충분하다.

풀이 계획

1. 리포트 돌면서 신고받은 아이디를 key값으로 하는 해시 테이블 초기화
2. 만들어진 해시 테이블 중 value의 길이가 2 이상인 key가 있다면,
   해당 key 값을 banned_id 리스트에 추가.
3. id_list 돌면서 신고한 아이디를 key 값으로 하는 해시 테이블2 초기화
4. banned_id 돌면서 reported_dic의 값 리스트 돌면서 report_dic에 +1

---

풀이 코드

Python

def solution(id_list, report, k):
  report = list(set(report))

  reported_dic = {}
  for i in report:
    ban_to, ban_from = i.split(' ')
    if ban_from in reported_dic:
      reported_dic[ban_from].append(ban_to)
    else:
      reported_dic[ban_from] = [ban_to]

  banned_id = []
  for ban_to, ban_list in reported_dic.items():
    if len(ban_list) >= k:
      banned_id.append(ban_to)

  report_dic = {}
  for i in id_list:
    report_dic[i] = 0

report_dic에 +1
  answer = []
  for i in banned_id:
    for j in reported_dic[i]:
      report_dic[j] += 1

  return list(report_dic.values())

커뮤니티 코드

# from collections import defaultdict


# def solution(id_list, report, k):
#   report = set(report)
#   collect = defaultdict(list)
#   answer_dic = defaultdict(int)

#   for i in id_list:
#     collect[i] = []
#     answer_dic[i] = 0
#   for i in report:
#     do, to = i.split(' ')
#     collect[to].append(do)
  
#   for i in collect.items():
#     if len(i[1]) >= k:
#       for j in i[1]:
#         answer_dic[j] += 1

#   return list(answer_dic.values())

배울 점.
defaultdict의 사용으로 코드가 깔끔해보이고 읽기 편하다.

Javascript

// function solution(id_list, report, k) {
//   let reports = [...new Set(report)].map(a => {return a.split(' ')})
//   let reportTo = new Map();
//   for(const bad of reports){
//     reportTo.set(bad[1], reportTo.get(bad[1])+1 || 1)
//   }
  
//   let reportFrom = new Map();
//   for(const bad of reports){
//     if (reportTo.get(bad[1]) >= k){
//       reportFrom.set(bad[0],reportFrom.get(bad[0])+1 || 1)
//     }
//   }

//   let answer = id_list.map(a => reportFrom.get(a) || 0 );
//   return answer;
// }