2022 카카오 신입공채 코딩테스트(1)

문제 출처 (프로그래머스)

해쉬 자료구조를 사용하면 제한시간 내에 해결할 수 있을 것 같다.
{"신고 당한 유저" : ["신고자1", "신고자2" ...] 이런 형태를 만들면 될 것
report의 길이는 최대 200,000이고 id_list의 최대 길이는 1,000이므로 최악의 경우 200,000,000
--> O(len(id_list) * len(report))

먼저 신고 당한 유저를 key로, 그 유저를 신고한 사람들을 리스트 형태의 value로 저장한다.
이때 중복이 있어도 1회로 취급하므로 편의를 위해 list대신 set자료형을 사용했다.

그리고 answer 딕셔너리를 하나 더 만들고 전체 유저를 key로한다. 위의 신고자 딕셔너리를 순회하면서 set의 길이가 k 이상이면 set에 포함된 유저들의 value에 +1을 해준다.

answer의 values를 list형태로 반환한다.

from collections import defaultdict

def solution(id_list, report, k):
    
    reported = defaultdict(set)    
    for content in report:
        repo, target = content.split()
        reported[target].add(repo)
        
    answer = {id: 0 for id in id_list}
    for name, history in reported.items():
        if len(history) >= k:
            for reporter in history:
                answer[reporter] += 1
    
        
    return list(answer.values())