[프로그래머스] 92334 신고 결과 받기 파이썬(Python)

오늘은 문자열 문제를 풀다가 만난 시간 복잡도 문제를 해결한 방법을 공유해보려고 한다.

문제 링크는 아래 참고!

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

프로그래머스

 

문제 이해하기

게시판 이용자 리스트인 id_list가 주어지고, 신고 리스트 report가 주어진다.

이때, report는 공백을 기준으로 "신고한 이용자 아이디 신고당한 이용자 아이디"로 이루어져 있다.

k번 이상 신고당한 이용자는 아이디 정지 조치를 받게 되는데, 이 이용자를 신고한 사람에게는 정지 조치를 했다는 메일을 보내게 된다.

(단, 한 명이 동일한 사람을 여러 번 신고하는 것은 신고횟수 1회로 처리된다.)

id_list의 각 사용자가 총 몇 개의 이메일을 받게 되는지 리스트로 반환해라.

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

 

접근 방법

이 문제의 제한 조건을 보며 worst case를 도출해보자.

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

 

조건을 살펴보면 id_list의 최대 길이는 10³이고, report의 최대 길이는 2 x 10⁵이다. 그런데 report는 "이용자id 신고한id"로 구성되어 있기 때문에 절반으로 나누면 이용자id가 최대 10⁵개, 신고당한id가 최대 10⁵개임을 알 수 있다.

따라서 이 문제는 O(n²)으로 풀면 안된다!

최대한 O(n)으로 풀어야되겠다는 생각이 든다. O(n)으로 풀기 위해서는 딕셔너리를 적극 이용해야겠다!

 

 

그 다음으로는 문제에 어떻게 접근할지 생각해보자.

우리가 도출해야하는 건 각 이용자가 받은 메일의 수이다. 이걸 구하기 위해 어떤 이용자가 정지되었는지를 먼저 알아야한다.

1. report의 값을 공백 기준으로 잘라서 신고한 이용자 id, 신고당한 이용자 id를 나눠야겠다.
2. 신고당한 이용자가 발생하면 해당 이용자에게 1을 더해준다.
3. 이때, 이미 같은 사람에게 신고를 당했다면 1을 더해주면 안된다.
4. 이렇게 report 리스트를 다 돌면서 신고 횟수를 기록했다면 이제 이 기록을 조회하면서 k번 이상 신고된 이용자를 정지시킨다.
5. 정지된 이용자를 신고한 이용자에게 이메일을 하나씩 보내면 끝

나는 문제를 풀기 전에 위처럼 로직을 구성했다.

 

 

이제 위 로직을 코드로 짜보면 아래와 같다.

def solution(id_list, report, k):
    report_users = {}
    reported_users = {}
    for user_id in id_list:
        report_users[user_id] = []
        reported_users[user_id] = 0
    
    for rep in report:
        user_id, reported_id = rep.split()
        if reported_id in reported_users and reported_id not in report_users[user_id]:
            reported_users[reported_id] += 1
        if user_id in report_users:
            report_users[user_id].append(reported_id)
    
    abandoned_id = {}
    for reported_user, cnt in reported_users.items():
        if cnt >= k:
            abandoned_id[reported_user] = True
    
    emails = {}
    for report_user, li in report_users.items():
        emails[report_user] = 0
        for reported_user in li:
            if reported_user in abandoned_id:
                emails[report_user] += 1
    
    return list(emails.values())

 

그런데 정확성 테스트 점수... 8.3/100 ....

 

나는 여기서 문제가 두 번째 for문에서 reported_id not in report_users[user_id]라고 생각했다.

왜냐하면 report_users[user_id]는 리스트인데 이 리스트를 순회하면서 reported_id가 있는지 없는지 확인하는 과정이 O(n)이기 때문이다. 이미 for 문으로 O(m)을 쓰고 있으니 이렇게 코드를 짜면 시간복잡도가 O(nxm)으로 나온다는 문제가 있었다.

 

이를 해결하기 위해 아, 그냥 report에서 중복을 제거해버리자. 라고 판단했고 아래와 같이 코드를 수정했다.

def solution(id_list, report, k):
    report_users = {}
    reported_users = {}
    for user_id in id_list:
        report_users[user_id] = []
        reported_users[user_id] = 0
    
    report = list(set(report))
    for rep in report:
        user_id, reported_id = rep.split()
        if reported_id in reported_users:
            reported_users[reported_id] += 1
        if user_id in report_users:
            report_users[user_id].append(reported_id)
    
    abandoned_id = {}
    for reported_user, cnt in reported_users.items():
        if cnt >= k:
            abandoned_id[reported_user] = True
    
    emails = {}
    for report_user, li in report_users.items():
        emails[report_user] = 0
        for reported_user in li:
            if reported_user in abandoned_id:
                emails[report_user] += 1
    
    return list(emails.values()

 

위 코드를 보면 report = list(set(report)) 라는 코드를 통해 report 리스트의 중복을 제거하고 있다.

이렇게 코드를 수정하니까

짠 통과!👏👏👏

 

 

 

---

 

시간복잡도 문제가 있다면 딕셔너리를 적극 활용해보는 것을 추천한다!

딕셔너리의 key in {dict} 연산은 O(1)의 말도 안되는 시간 복잡도를 자랑하기 때문에 이를 활용하면 시간 복잡도를 엄청나게 줄일 수 있다!!

https://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity

Python dictionary keys. "In" complexity