[노씨데브 킬링캠프] 5주차 - 문제풀이: 신고 결과 받기

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

이전에 풀었던 기록

'''
아
id_list chk matrix 생성(n*n)
for report
    report[0] -> report[1] 방문여부 체크
    if 방문했음
        pass
    elif 방문 안했음
        report[1] 신고횟수 ++
        방문여부 True 변환
for 최종방문횟수
    if 횟수 > k
        방문여부확인리스트[현재정지자인덱스] 값이 True 값인 신고자 index 전부 추출후
        result++
    
시
1,000*1,000 = 1,000,000 << 2억

자
id_list chk matrix : bool[][]
id_list_최종신고횟수리스트 : int[]
'''

def solution(id_list, report, k):
    answer = [0 for _ in range(len(id_list))]
    chk = [[False]*len(id_list) for _ in range(len(id_list))]
    report_score = [0 for _ in range(len(id_list))]
    
    for i in range(len(report)):
        ter = report[i].split()[0]  
        tee = report[i].split()[1]
        if chk[id_list.index(ter)][id_list.index(tee)] == False:
            chk[id_list.index(ter)][id_list.index(tee)] = True
            report_score[id_list.index(tee)] += 1
    
    for i in range(len(report_score)):
        if report_score[i] >= k:
            for j in range(len(id_list)):
                if chk[j][i] == True:
                    answer[j] += 1
    
    return answer

문제 파악 [필수 작성]

문제이해

1인당 신고제한은 없음
단, A->B 여러번신고시 누적은 1회 만
신고당한사람 카운트 k 넘을시 정지

제한 조건 확인

아이디어

A->B 신고하면
key: B -> value: Set([A,...]) 형식으로 구현

시간복잡도

report 길이만큼 반복 후
id_list 만큼 반복
-> 충분

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

#15분소요
from collections import defaultdict
def solution(id_list, report, k):
    mail_dict = defaultdict(int)
    report_dict = defaultdict(set)
    for r in report:
        A,B = r.split()
        report_dict[B].add(A)
    for reported in report_dict:
        if len(report_dict[reported]) >= k:
            for reporter in report_dict[reported]:
                mail_dict[reporter] += 1
    answer = []
    for name in id_list:
        answer.append(mail_dict[name])

    return answer

배우게 된 점 [필수 작성]

자유 형식

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.