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

문제: 신고 결과 받기

풀이

# 각 유저는 한 번에 한 명의 유저를 신고할 수 있다. 신고 횟수에 제한은 x, 동일한 유저에 대한 신고 횟수는 1회로 처리됨

# k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송
# 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송

# 이용자, [이용자id, 신고한id 형태의 문자열],
def solution(id_list, report, k):
    answer = []

    id_set_dict = {id_: set() for id_ in id_list}
    id_email_cnt = [0] * len(id_list)

    for i in range(len(report)):
        reporter, black = report[i].split()
        id_set_dict[black].add(reporter)

    for i in range(len(id_list)):
        if len(id_set_dict[id_list[i]]) >= k:
            for j in id_set_dict[id_list[i]]:
                id_email_cnt[id_list.index(j)] += 1

    # id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 된다.
    return id_email_cnt

• 동일한 유저에 대한 신고 횟수 1회로 처리 -> set
• k번 이상 신고된 유저의 id 순서대로 count

👀 시간 복잡도 O(n^2)

GPT가 개선해준 코드

from collections import defaultdict

def solution(id_list, report, k):
    answer = []

    # 각 유저가 신고한 이용자들을 저장하는 딕셔너리
    report_dict = defaultdict(set)
    # 각 유저가 받은 신고 횟수를 저장하는 딕셔너리
    report_count = defaultdict(int)

    # 신고 기록을 파싱하여 딕셔너리에 저장
    for r in report:
        reporter, reported = r.split()
        # 신고자가 이미 해당 유저를 신고한 경우를 제외하기 위해 집합을 사용
        if reported not in report_dict[reporter]:
            report_dict[reporter].add(reported)
            report_count[reported] += 1

    # 정지된 유저를 파악하여 해당 유저를 신고한 유저들에게 결과 메일을 전송
    for user in id_list:
        suspended_count = sum(1 for reported_user in report_dict[user] if report_count[reported_user] >= k)
        answer.append(suspended_count)

    return answer

suspended_count = sum(1 for reported_user in report_dict[user] if report_count[reported_user] >= k)

이 부분을 풀어서 쓰면 아래와 같다.

suspended_count = 0  # 해당 유저에게 전송될 결과 메일의 수를 나타내는 변수를 초기화합니다.

# 해당 유저가 신고한 모든 이용자에 대해 반복합니다.
for reported_user in report_dict[user]:
    # 신고 횟수가 정지 기준을 넘었는지 확인합니다.
    if report_count[reported_user] >= k:
        # 정지 기준을 넘은 경우, 해당 이용자는 정지되므로 결과 메일의 수를 1 증가시킵니다.
        suspended_count += 1

👀 시간 복잡도 O(N + M)

• report 리스트의 길이를 N
• id_list의 길이를 M

defaultdict란?

• dict 클래스와 비슷하지만, 존재하지 않는 키에 접근할 때 오류를 발생시키지 않고, 기본값을 반환하는 기능을 제공하는 클래스
• 일반적인 딕셔너리를 사용할 경우, 해당 키가 존재하는지 먼저 확인해야 하고, 존재하지 않는 경우에는 초기값을 할당한 후에 값을 증가시켜야 한다. 반면에 defaultdict를 사용하면 이러한 과정을 생략하고 즉시 값을 증가시킬 수 있다

참고