[프로그래머스][Python] 신고 결과 받기
진짜 오랜만에 올리는 코테 풀이..!
🚨
https://school.programmers.co.kr/learn/courses/30/lessons/92334
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
🪼 문제 요약
유저는 한 번에 다른 한 명의 유저를 신고할 수 있다. 이때, 중복 신고도 가능하나 집계는 되지 않는다. (1회로 간주)
k번 이상의 신고를 받은 유저는 정지당한다.
정지당한 유저를 신고한 모든 유저에게 메일이 간다.
모든 유저의 메일을 받은 총횟수를 배열로 반환하면 된다.
⚠️ 첫 번째 풀이 - 시간초과 발생
def solution(id_list, report, k):
mail = {}
report_id = {}
reported_id = {}
for id in id_list:
mail[id] = 0
for r in report:
id1, id2 = r.split()
if id1 in list(report_id.keys()):
if (id2 not in report_id[id1]):
report_id[id1].append(id2)
else:
report_id[id1] = [id2]
if id2 in list(reported_id.keys()):
if (id1 not in reported_id[id2]):
reported_id[id2].append(id1)
else:
reported_id[id2] = [id1]
stop_id = [key for key, value in reported_id.items() if len(value) >= k]
for stop in stop_id:
for key, value in report_id.items():
if stop in value:
mail[key] += 1
ans = list(mail.values())
return ans
아예 틀린 게 아니라 시간 초과인 거라서 반복문을 줄이면 해결될 것 같은데, 어떻게 해야 될지 모르겠었다.
✅ 정답 코드
def solution(id_list, report, k):
mail = {id: 0 for id in id_list}
report_id = {id: set() for id in id_list}
reported_count = {id: 0 for id in id_list}
# 중복 제거한 신고 기록 처리
for r in set(report):
reporter, target = r.split()
report_id[reporter].add(target)
reported_count[target] += 1
# 정지된 유저 목록
stopped_users = {id for id, count in reported_count.items() if count >= k}
# 메일 보낼 횟수 계산
for reporter in id_list:
mail[reporter] = sum(1 for target in report_id[reporter] if target in stopped_users)
return list(mail.values())
지선생님에게 도움을 청했다.
불필요한 반복을 줄이고, 복잡한 로직을 단순화해 줬다.
딱 봐도 엄청 간단해지긴 했는데, 정작 다시 풀어보라고 하면 못할 것 같아서 블로그 주제로 데려왔다.
순차적으로 뜯어보자 !
🐟 코드 설명
우선 수정 전과 수정 후 코드에서 모두 딕셔너리 3개를 두는 건 동일하지만, 차이점이 하나 있다.
신고당한 사람을 id로, 신고한 사람을 value로 두었던 reported_id에서
유저별로 신고당한 횟수만 저장하는 reported_count로 바뀌었다. 신고한 사람에 대한 정보는 저장하지 않는다.
신고한 사람의 정보는 report_id에 이미 다 들어 있기 때문이다.
누가 누구를 신고했는지 알 수 있다면, 반대로 신고당한 사람을 신고한 사람이 누구인지도 역추적 가능하다.
중복된 정보를 또 저장하는 것은 불필요한 연산을 늘릴 수 있다.
[ 최종 딕셔너리 ]
mail: 유저별 메일을 받은 횟수 저장
report_id: 신고한 유저와 신고당한 유저 아이디 저장
reported_count: 유저별 신고당한 횟수 저장
여기서 처음 보는 방식이 등장했다.
기존 코드
for id in id_list:
mail[id] = 0
수정 후 코드
mail = {id: 0 for id in id_list}
한 줄로 간단하게 초기화시켜 줄 수 있다.
id를 key로, 0을 value로 설정한 딕셔너리가 생성된다.
report_id = {id: set() for id in id_list}
마찬가지의 방식으로 딕셔너리를 생성한다.
차이는 report_id의 value는 set으로 초기화한다.
중복 신고가 가능하나 집계는 되지 않는다. (1회로 간주)
해당 조건을 충족시키기 위해 아예 처음부터 set으로 설정해 주는 것이다.
기존 코드에서는 같은 신고 건수가 딕셔너리에 존재하는지를 매번 if문으로 확인하면서 데이터를 추가할지 말지를 결정했었다.
이러면 불필요한 연산이 발생할 수 있다.
# 중복 제거한 신고 기록 처리
for r in set(report):
reporter, target = r.split()
report_id[reporter].add(target)
reported_count[target] += 1
외부에서 제공되는 report는 신고한 유저와 신고당한 유저를 공백으로 구분한 문자열의 배열이다.
여기에서 report를 set으로 만들어서 for문을 돈다.
이 코드를 보고 처음에는
왜 또 set을 적용하지? report_id를 어차피 set으로 선언해 뒀기 때문에 알아서 중복이 제거되지 않나?
라는 생각을 했었다.
그런데 다시 보니까 필수로 적용해주어야 하는 사항이다.
내 생각대로 report_id는 value가 set이기 때문에, 같은 신고의 경우 자동으로 중복이 제거된다.
즉, report_id만 보면 중복 신고 여부는 문제가 되지 않는다.
그렇지만 바로 다음 줄에서 문제가 생긴다.
중복 값이 들어와도 reported_count는 중복 여부를 알 수 없기 때문에, 항상 1씩 증가시켜 버린다.
따라서 중복 신고를 여러 번의 신고로 간주하게 되는 문제가 발생하게 된다. 🚨
# 정지된 유저 목록
stopped_users = {id for id, count in reported_count.items() if count >= k}
k번 이상의 신고를 당한 유저의 아이디를 stopped_users에 저장한다.
이때, stopped_users는 set 컴프리헨션 문법을 사용하여 생성되며, 자료형은 set이다.
만약 대괄호 []를 사용했다면 리스트(list)가 생성되었을 것이다.
뒤에서 in 연산을 사용하게 될 텐데, 이때 set을 사용하는 것이 배열을 사용하는 것보다 빠르다.
🐬 리스트의 in 연산 시간 복잡도 - O(N)
🐬 set의 in 연산 시간 복잡도 - O(1)
# 메일 보낼 횟수 계산
for reporter in id_list:
mail[reporter] = sum(1 for target in report_id[reporter] if target in stopped_users)
모든 유저를 순회하며, 각 유저가 받을 메일 수를 계산한다.
report_id[reporter]는 해당 유저가 신고한 유저들의 집합이다.
이 집합을 돌면서, 각 신고 대상이 정지된 유저 목록(stopped_users)에 포함되어 있는지를 확인한다.
정지된 유저일 경우 1로 간주하고, sum()을 통해 최종적으로 정지된 유저 수를 도출한다.
결과적으로 이 값은 해당 유저가 신고한 유저 중 실제로 정지된 유저의 수가 된다.
🪼 마무리
어렵긴 해도 나름 코드를 이해는 했다고 생각했는데,
심지어 이 글을 작성하면서 잘못 이해하고 있던 새로운 부분들을 몇 가지 발견했다.
정리해 보길 잘한 것 같다 ..!
앞으로는 효율적으로 문제를 해결하는 습관을 들여야겠다 .. ㅎㅎ
(시간복잡도 신경 안 쓰고 풀다가 큰코다치는 사람)