[Lv1. 신고 결과 받기] 풀이 기록

처음 제출한 답

• 뭔가 딕셔너리로 풀어야 될 거 같은데 잘 안떠올라서 for문 덕지덕지로 일단 해결

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

    matrix = [[0] * len(id_list) for _ in range(len(id_list))]
    report_count = dict()
    id_list_len = len(id_list)

    for i in range(id_list_len):
        report_count[id_list[i]] = 0

    for r in report:
        reporter, bad_man = r.split(" ")
        r_index = id_list.index(reporter)
        b_index = id_list.index(bad_man)
        
        if matrix[r_index][b_index] == 0:
            matrix[r_index][b_index] += 1
        
    for y in range(id_list_len):
        count = 0
        for x in range(id_list_len):
            if matrix[x][y] == 1:
                count += 1
        if count >= k:
            for z in range(id_list_len):
                if matrix[z][y] == 1:
                    report_count[id_list[z]] += 1
    
    for i in id_list:
        answer.append(report_count[i])

    return answer

 

성능 보니까 딱 봐도 느려보인다.

 

다른 사람의 풀이 보고서 set + 딕셔너리로 푸는 것 확인

 

두번째 풀이

• set 쓴 거 보고 허탈했다.
• answer를 저렇게 0으로 세팅하고 reporter의 인덱스를 찾아서 1씩 더해주는 방법

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    reports = {x : 0 for x in id_list}

    for r in set(report):
        bad_man = r.split(" ")[1]
        reports[bad_man] += 1
    
    for r in set(report):
        bad_man = r.split(" ")[1]
        if reports[bad_man] >= k:
            reporter = r.split(" ")[0]
            reporter_index = id_list.index(reporter)
            answer[reporter_index] += 1

    return answer

 

성능을 보면 작게는 2배에서 크게는 10배까지 줄어들었다.

근데 index() 가 전체를 순회해서 이것도 느린 거라고 한다.

그럼 index()를 쓰지 말고 풀어보자

 

마지막 풀이

• user_index라는 딕셔너리를 통해 각 user별 value를 바로 +1 시켜주고  answer에는 value 들만 더해주는 방식

def solution(id_list, report, k):
    answer = []
    reports = {x : 0 for x in id_list}
    user_index = {x : 0 for x in id_list}

    for r in set(report):
        bad_man = r.split(" ")[1]
        reports[bad_man] += 1
    
    for r in set(report):
        bad_man = r.split(" ")[1]
        if reports[bad_man] >= k:
            reporter = r.split(" ")[0]
            user_index[reporter] += 1

    for i in id_list:
        answer.append(user_index[i])

    return answer

 

성능이 1, 2번 대비 눈에 띄게 좋아진 것 확인