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

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

프로그래머스

---

문제 풀이 1.

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    report_dict = {key: set() for key in id_list}
    mail_dict = {key: 0 for key in id_list}
    
    for report_item in report:
        report, reported = report_item.split(' ')
        if reported not in report_dict[report]:
            mail_dict[reported] += 1
            report_dict[report].add(reported)
    
    for name in id_list:
        if mail_dict[name] >= k:
            for report in report_dict.keys():
                if name in report_dict[report]:
                    answer[id_list.index(report)] += 1
        
    return answer

 

report_dict : key - id_list 신고자 , value - 신고자 key가 신고한 사람들의 set (중복 제거를 피하기 위함이었지만 아래 if 문에서 피해가므로 제 역할은 하지 않음)

mail_dict : key - id_list 신고 당한 사람 , value - 신고당한 횟수 (숫자)

 

첫 번째 for 문 : report_dict 와 mail_dict 를 채움.

 

두 번째 이중 for 문 : id_list의 이름을 순차적으로 확인하면서 mail_dict의 value값이 k 값 이상인 이름이 set에 존재하는 report_dict의 key값의 id_list값을 가져와 해당 answer 인덱스에 더함. (약간 복잡..)

---

문제 풀이 2. 

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    n = len(id_list)
    
    report_graph = [[0] * n for _ in range(n)]
    
    for report_item in report:
        report, reported = report_item.split(' ')
        report_graph[id_list.index(report)][id_list.index(reported)] = 1
    
    reported_list = [0] * n
    for c in range(n):
        cnt = 0
        for r in range(n):
            cnt += report_graph[r][c]
        reported_list[c] = cnt
    
    for r in range(n):
        for c in range(n):
            if report_graph[r][c] == 1 and reported_list[c] >= k:
                answer[r] += 1
    
    return answer

 

문제는 이런 형태의 인접 행렬로 나타낼 수 있다.

위의 인접 행렬을 방향성을 고려하여 그려보면 위와 같다.

그리고 위의 인접행렬을 자세히 보면 이렇게 나타낼 수 있겠다.

이를 이용하여 reported_list에는 신고당한 횟수를 기록하였고, 그래프를 돌아 해당 노드로 가는 간선이 있다면 answer에 값을 누적하였다.

 

---

 

지난 PCCP 강의에서 풀었던 문제다. 어떻게 푸느냐가 레벨을 다르게 할 수 있다고 하셨던 강사님의 말씀이 인상깊다.