[2022 KAKAO BLIND RECRUITMENT] 신고 결과 받기

⭐️ 신고 결과 받기

 

📝 설계

우선 문제를 꼼꼼히 읽어야 겠다는 생각을 했습니다.. 가장 큰 제약 조건은 신고한 사람이 같은 사람을 또 신고했을 때, 신고 횟수는 늘어나지 않는다는 것입니다. 또, 문제에서 매개변수로 준 id_list, report, k라는 조건을 모두 활용하려고 노력했습니다.

제 풀이는 defaultdict을 이용했는데 이때 신고횟수를 세는 딕셔너리 한개와 누가 누구를 신고했는지 기록하는 딕셔너리 한개를 만들었습니다. 그리고, 누가 누구를 신고하고 신고횟수를 카운팅해주었는데, 예를들어 a가 b를 신고했을 때 b가 a의 신고 리스트에 들어있다면 신고 횟수를 늘리지 않았습니다. 그리고 그 두개의 딕셔너리에 대해 2중 for문을 돌면서, 탐색을 진행했습니다. 신고 횟수가 k 이상인 사람에 대하여, 신고 당한 사람이 신고한사람과 신고당한사람의 관계의 딕셔너리에 value값의 리스트에 포함된다면. 그 신고한사람에 해당하는 인덱스에 존재하는 숫자를 증가시켜야합니다.

 

다음은 실제 풀이하면서 작성한 코드입니다.

 

from collections import defaultdict
def solution(id_list, report, k):
    answer = [0] * len(id_list)
    # print(id_list)
    singo_count = defaultdict(int)
    who_singo_who = defaultdict(list)

    for e in report :
        a,b = e.split(" ")
        if b not in who_singo_who[a]:
            who_singo_who[a].append(b)
            singo_count[b] += 1
    # print(who_singo_who)
    # print(singo_count)
    for a,b in singo_count.items():
        if b>=k :
            # a는 신고 당한사람
            # c는 신고 한사람
            for c,d in who_singo_who.items():
                if a in d:
                    idx = id_list.index(c)
                    # print(a, d, idx)
                    answer[idx] += 1

    return answer

 

개선해야 하는 부분이 있기 때문에 문제를 다 풀고 나서 코드를 개선해 보았습니다. 이때 다른사람의 풀이와 카카오 기술 블로그를 참고하였습니다.

 

우선 프로그래머스 좋아요를 가장 많이 받은 풀이입니다.

 

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

    for r in set(report):
        reports[r.split()[1]] += 1

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

    return answer

 

reports를 저런 방식으로 할당하는건 좋았고, set으로 겹치는거 삭제하는건 너무 좋은 것 같습니다. 풀이가 진짜 이쁩니다.

 

이제 기술 블로그를 읽어보겠습니다. 일단 이문제는 해시 자료구조를 활용할 수 있는지 묻는 입니다. 리포트를 하나씩 처리하면서 각 유저가 누구에게 신고를 당했는지 목록을 만들고, 유저아이디는 최대 1000개, report의 길이는 최대 200,000이므로 신고된 유저 아이디를 배열에 관리한다면 최악의 경우 O(아이디개수*리포트 길이) 만큼의 시간이 걸립니다.

따라서 신고된 유저 아이디를 해시 자료구조를 이용해 관리하면 효율적으로 목록을 완성할 수 있습니다. 이때 신고한 유저 목록에는 같은 아이디가 중복해서 들어가지 않도록 주의합니다. 위와 같이 목록을 만들었다면 신고된 유저 아이디를 순회하면서 정지 기준을 만족하는 유저가 있다면 신고한 유저가 k이상이면 신고한 유저 목록을 순회하면서 메일을 보냈다는 표시(카운트 1증가)를 해주면 됩니다.

 

 

마지막으로 자바스크립트 풀이를 익혀보면서 마치겠습니다.

function solution(id_list, report, k) {
    let reports = [...new Set(report)].map(a=>{return a.split(' ')});
    let counts = new Map();
    for (const bad of reports){
        counts.set(bad[1],counts.get(bad[1])+1||1)
    }
    let good = new Map();
    for(const report of reports){
        if(counts.get(report[1])>=k){
            good.set(report[0],good.get(report[0])+1||1)
        }
    }
    let answer = id_list.map(a=>good.get(a)||0)
    return answer;
}