코딩을 점점 공부를 하면서 느꼈던건 오늘배우거나
알게된것 즉, TIL(Today I Learned) 을 정리 해야 하겠다는 생각이 들었다.
매번 새로운것을 배우지만 금방 잊어버리고 새로운 것을 또 찾아보는 나...
TIL을 작성하는 습관을 통해 고쳐보고자 한다.
오늘의 TIL 주제는 어제 풀다가 그만둔 알고리즘 문제에 시간을 많이 썼기에 관련 내용을 적어볼 생각이다.
하루 반나절 걸려 풀었던 문제는 2022 KAKAO BLIND RECRUITMENT 에 나왔던 문제로 신고 결과 받기 문제..(level1 인데..🥲)
우선 간략한 문제설명은 다음과 같다
- 각 유저는 한번에 한명만 신고 가능.
신고 횟수에 제한은 없다, 서로 다른 유저를 계속해서 신고할 수 있음.
한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리.- k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송한다.
- 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송한다.
입출력 예
id_list = ["muzi", "frodo", "apeach", "neo"]
report = ["muzi frodo","apeach frodo",
"frodo neo","muzi neo","apeach muzi"]
# report의 경우 각 스트링의 공백기준 앞은 신고한 유저, 뒤는 신고당한 유저 이다.
k = 2
result = [2,1,1,0]
제한사항
2 ≤ id_list의 길이 ≤ 1,000
1 ≤ report의 길이 ≤ 200,000
1 ≤ k ≤ 200, k는 자연수입니다.
아래는 최종적으로 작성해본 코드이다.
def solution(id_list, report, k):
answer = []
rep_dict ={}
report = set(report)
for i in id_list: # 유저수 만큼 리포트 요청 dict 초기화
rep_dict[i] = []
answer.append(0)
for r_item in report:
r_user=r_item.split()[0] # 신고한 유저
b_user=r_item.split()[1] # 신고 받은 유저
rep_dict[b_user].append(id_list.index(r_user))
for r_log in rep_dict.values():
if len(r_log) >= k:
for r_log_item in r_log:
answer[r_log_item] += 1
return answer이와 같이 작성 하였는데 이번 문제의 핵심은 report를 다중for 문으로 돌리지 않는것이 핵심이였던것 같다. 위 코드로는 테스트 케이스를 통과 했으나 처음 작성했던 코드의 경우 report 리스트를 다중for 문으로 즉 시간복잡도가 O(n^2) 이 되었었는데 (report 의 경우 최악의 경우 200,000^2 ) 이때 대다수의 test case 에서 통과 하지 못하는 경우가 발생했다.
그리고 몇몇 테스트 결과또한 실패로 출력이 되었는데 코드의 마지막 에서
4번째에 있는 라인의 조건문의 조건을 잘못 설정한 문제였다. 처음엔 위와 같은 형태가 아닌 if len(r_log) == k : 의 형태로 즉 신고횟수가 k 번 이상이 아닌 k 일때만 아래의 루프가 실행되기에 입출력 예의 경우는 통과 하지만 k번 이상 신고받은 유저의 경우는 신고한 유저에게 신고결과 메세지 발송 카운트를 해주지 못하였던 것... 다음부턴 문제를 잘 읽어야 할것 같다... 🦦
