프로그래머스 신고 결과 받기(Python)

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

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

이 것도 레벨 1 문제라 풀이 방법을 생각해내는데 오래 걸리지 않았다. 현재 내 실력은 레벨 1 정도가 적당한가 보다...

다 풀고 나서 다른 사람들의 풀이를 봤는데 감명 깊었던 풀이가 있어 그 풀이로 다시 풀어봤더니 걸리는 시간의 차이가 엄청났다.

나의 풀이

나는 누구를 신고했는지(report_to), 누가 몇 번 신고받았는지(reported_cnt) 각각 dictionary로 저장해서 파악했다.

report_to의 value는 id들을 담기 위해 빈 리스트로, reported_cnt는 횟수를 세야 하기에 value를 0으로 초기화했다.

마지막에 받을 메일의 개수를 세는 계산은 마지막의 이중 for문으로 했다. 실제로 정지당한 아이디가 포함된 곳을 찾기 위해 dictionary의 모든 key값을 탐색했다. 정지 당한 아이디를 신고한 아이디를 찾아 id_list에서의 인덱스(answer의 인덱스와 같기 때문이다.)를 찾아 메일의 개수를 계산한다.

지금까지의 설명을 python으로 작성한 것이 아래의 코드다.

def solution(id_list, report, k):
    # Setting Variables
    answer = [0] * len(id_list)
    report_to, reported_cnt = {}, {}
    for id_str in id_list:
        report_to[id_str] = []
        reported_cnt[id_str] = 0
    
    # Counting Report
    for log in report:
        reporter, reported = log.split()
        if reported not in report_to[reporter]:
            report_to[reporter].append(reported)
            reported_cnt[reported] += 1
    
    # Collect if report count >= k and calculate mail count for each
    collected = [key for key, val in reported_cnt.items() if val >= k]
    for id_str in collected:
        for key in report_to:
            if id_str in report_to[key]:
                answer[id_list.index(key)] += 1
    return answer

채점 시 최대로 4723.82 ms, 37.7MB만큼의 자원을 소비했다.

감명받은 풀이

https://programmers.co.kr/learn/courses/30/lessons/92334/solution_groups?language=python3

프로그래머스

이 풀이에서 중요한 것은 'set'이다. 파이썬에서의 set은 집합을 의미한다. 집합에서의 정의처럼 파이썬의 set에도 중복 원소는 존재할 수 없다.

집합의 원소는 서로 다르며, 같은 원소가 여러 개 있을 수는 없다.
https://ko.wikipedia.org/wiki/%EC%A7%91%ED%95%A9

set([iterable]) 과 같이 set 생성자의 인자로 iterable 객체를 넣어주면 iterable 객체 안에서 중복되는 원소의 값은 하나만 남긴 set 객체로 생성할 수 있다. 이 문제에서의 경우 report를 set으로 바꾸면 중복 신고한 내용은 하나만 남게 된다!

set을 사용하면서 마지막 이중 for문이 단일 for문으로 바뀌었다.

set을 적용한 코드는 아래와 같다. 확실히 위의 코드보다 짧아졌고, 간결해 보인다.

def solution(id_list, report, k):
    # Setting Variables
    answer = [0] * len(id_list)
    reported_cnt = {id_str : 0 for id_str in id_list}
    minimized_report = set(report)
    
    # Counting Report
    for log in minimized_report:
        reporter, reported = log.split()
        reported_cnt[reported] += 1
    
    # if report count >= k, calculate mail count for each reporter
    for log in minimized_report:
        reporter, reported = log.split()
        if reported_cnt[reported] >= k:
            answer[id_list.index(reporter)] += 1
    return answer

이 코드로 채점할 때, 최대 1194.92 ms, 39.6MB의 자원을 소모했다.

이전 코드보다 거의 4배나 시간을 단축시켰다.

 

python을 사용하는 유저로서 파이썬의 자료 구조들(list, dictionary, set)을 파악하고 있어야겠다고 생각이 들었다.