[level 1] 신고 결과 받기

문제

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

• 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
  • 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
  • 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
• k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
  • 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.

 

따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다.

이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

 

문제 풀이 접근법1

1) id_list와 set(report)로 이중 반복문을 돌린다. 이때, i(id_list의 각 원소)와 one(j.split의 원소의 첫번째, 즉 신고자)가 같다면 tmp리스트에 two(신고 당한 사람)를 추가한다. 

2) 만약 two가 report_count딕셔너리에 있다면 two를 key로 하는 report_count의 value에 1을 추가하고(신고 당한 횟수) 없다면 two를 key로 하는 report_count의 value를 1로 정의한다. 

3) 어떤 유저가 어떤 유저를 신고했는지 확인하기 위한 딕셔너리 user_report_list에 user_id를 key로 tmp를 value로 추가한다. 

4) answer를 0으로 채운다. 

5) report_count의 value가 k이상이면 해당 key를 stop_id에 추가한다.

6)  user_report_list의 value에 stop_id에 해당하는 id가 있으면 answer에 +1을 한다. (어차피 user_report_list의 key순서랑 list_id, answer 순서 같으므로) 

def solution(id_list, report, k):
    answer = []
    
    users_report_list = {}
    reports_count = {}
    stop_id = []

    for i in id_list:
        tmp = []
        for j in set(report): 
            one, two = j.split(" ")
            if i == one:
                tmp.append(two)
                if two in reports_count:
                    reports_count[two] +=1
                else:
                    reports_count[two] = 1

        users_report_list[i] = tmp
        answer.append(0)

    for i in list(reports_count):
        if reports_count[i] >= k:
            stop_id.append(i)

    for i in range(len(list(users_report_list))):
        user = list(users_report_list)[i]

        for j in stop_id:
            if j in users_report_list[user]:
                answer[i]+=1
            
    return answer

테스트 케이스 3, 9, 10, 11, 14, 15, 20, 21에서 시간초과가 되었다. 

 

 

 

문제 풀이 접근법2

1) count_report를 0으로 채운다.

2)  id_list와 set(report)로 이중 반복문을 돌린다. 이때, id_list[i]와 one이 같다면 tmp에 two을 추가한다. 만약 id_list[i]와 two가 같다면 count_report[i]에 +1을 한다. (answer, count_report, list_Id의 유저 순서가 다 똑같으므로 가능)

3) 어떤 유저가 어떤 유저를 신고했는지 확인하기 위한 딕셔너리 user_report_list에 user_id를 key로 tmp를 value로 추가한다. 또한 answer를 0으로 채운다(1에서 해도 되는데 왜...여기서...했을까..)

4) count_report[i]가 k 이상이면 stop_id에 id_list[i]를 추가한다.

5) user_report_list의 value에 stop_id에 해당하는 id가 있으면 answer에 +1을 한다

def solution(id_list, report, k):
    answer = []
    
    count_report = []
    user_report_list = {}
    stop_id = []

    for i in id_list:
        count_report.append(0)

    for i in range(len(id_list)):
        tmp = []
        for j in set(report):
            one, two = j.split(" ")
            if id_list[i] == one:
                tmp.append(two)
            if id_list[i] == two:
                count_report[i] +=1

        user_report_list[id_list[i]] = tmp
        answer.append(0)

    for i in range(len(count_report)):
        if count_report[i] >= k:
            stop_id.append(id_list[i])



    for i in range(len(list(user_report_list))):
        user = list(user_report_list)[i]
        for j in stop_id:
            if j in user_report_list[user]:
                answer[i] +=1
            
    return answer

역시나 테스트 케이스 3, 9, 10, 11, 14, 15, 20, 21에서 시간초과가 되었다.

아마도 user_report_list 만들 때 시간 복잡도가 많이 사용되나봄...!!

report가 최대 20만개라서..이중 반복문으로 하면 안될 것 같음

하...돌겠네요

 

 

문제 풀이 접근법3(성공)

1) answer는 0으로 채우고, user_report_list(어떤 유저가 어떤 유저를 신고했는지 기록하는 딕셔너리)는 for문으로 유저의 id(key): [] value, 리스트) 식이 되도록 한다. count_reprot(유저가 신고당한 횟수를 기록하는 딕셔너리)는 유저 id(key): 0(value)으로 선언한다. 마지막으로 정지할 유저의 id를 담을 리스트 stop_id를 선언한다.

2) report의 중복을 제거하기 위해 report를 set으로 변환한 후, 공백 문자를 기준으로 report의 원소를 나누어 각각 one(신고한 사람)과 two(신고 당한 사람)에 저장한다. 

count_report[two]의 value에 +1을 하고, user_report_list[one]의 value에는 two를 추가해준다. 

3) count_report[i]가 k 이상이면 stop_id에 id_list[i]를 추가한다

4) user_report_list의 value에 stop_id에 해당하는 id가 있으면 answer에 +1을 한다

def solution(id_list, report, k):
    answer = [0 for i in range(len(id_list))]
    user_report_list = {i:[] for i in id_list}
    count_report = {i:0 for i in id_list}
    stop_id = []

    for i in set(report):
        one, two = i.split()

        count_report[two] +=1
        user_report_list[one].append(two)

    for i in list(count_report):
        if count_report[i] >=k:
            stop_id.append(i)


    for i in range(len(list(user_report_list))):
        user = list(user_report_list)[i]
        for j in stop_id:
            if j in user_report_list[user]:
                answer[i] +=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

유저별 신고당 한 횟수를 딕셔너리에 저장하고

다시 for문을 돌려서 split()[1] (==신고 당한 사람)의 횟수가 k이상이면 split()[0]의 인덱스를 id_list에서 찾아서 answer[i]에 +1을 하는 건데

진짜 깔끔하돠...

 

def solution(id_list, report, k):
    answer = [0] * len(id_list)
    dic_report = {id: [] for id in id_list} # 해당 유저를 신고한 ID
    for i in set(report):
        i = i.split()
        dic_report[i[1]].append(i[0])

    for key, value in dic_report.items():
        if len(value) >= k:
            for j in value:
                answer[id_list.index(j)] += 1

    return answer

 

---

드디어...프로그래머스 level 1의 문제를 다 풀었다!!

이제 level 1문제 복습 + level 2문제 풀어야지

아좌좌 화이팅!!