프로그래머스 - 신고 결과 받기 (2021 KAKAO Blind Recruitment) / Level 1

문제 📋

코딩테스트 연습 - 신고 결과 받기

풀이 📝

from collections import defaultdict


def solution(id_list, report, k):
    report_id_dict = defaultdict(list)
    report_dict = defaultdict(int)
    email_dict = defaultdict(int)

    for i in id_list:
        email_dict[i] = 0

    for i in report:
        ids = i.split()
        if ids[1] not in report_id_dict[ids[0]]:
            report_id_dict[ids[0]].append(ids[1])
            report_dict[ids[1]] += 1

    for i in report_id_dict.keys():
        for j in report_id_dict[i]:
            if report_dict[j] >= k:
                email_dict[i] += 1

    return list(email_dict.values())

입력으로 들어온 id_list 길이가 최대 1,000이고 report의 최대 길이가 200,000 이기 때문에 단순히 순회하면 안된다고 판단했고 dictionary를 만들기로 했다.

총 3개의 dict을 만들었으며 누가 누구를 신고했는지 저장한 report_id_dict,
아이디당 신고횟수를 저장한 report_dict,
마지막으로 해당 아이디로 보내야 되는 email 수를 저장한 email_dict를 만들었다.

그렇게 하면 딕셔너리에 저장된 값들은 상수 시간에 접근 할 수 있어서 시간복잡도를 줄일 수 있다.