2022 KAKAO 코딩테스트 1차 1번 풀이

문제 설명

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

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

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

 

제한사항

• 2 ≤ id_list의 길이 ≤ 1,000
• 1 ≤ id_list의 원소 길이 ≤ 10
• id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
• 1 ≤ report의 길이 ≤ 200,000
• 3 ≤ report의 원소 길이 ≤ 21
• report의 원소는 “이용자 id 신고 id”형태의 문자열입니다.
• 예를 들어 “muzi frodo”의 경우 “muzi”가 “frodo”를 신고했다는 의미입니다.
• id는 알파벳 소문자로만 이루어져 있습니다.
• 이용자 id와 신고 id는 공백(스페이스) 하나로 구분되어 있습니다.
• 자기 자신을 신고하는 경우는 없습니다.
• 1 ≤ k ≤ 200, k는 자연수
• return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

소스코드

from collections import defaultdict


def solution(id_list, report, k):
    answer = [0] * len(id_list)
    
    # 주어지는 report 리스트를 중복 제거 해주는 것이 이 문제의 핵심이었다.
    # 이 한줄의 코드 없이 제출하면 수많은 시간초과를 만날 수 있다.
    report = set(report)
    
    user_list_who_i_report = defaultdict(set)
    num_of_reported = defaultdict(int)
    suspended = []

    for r in report:
        do_report, be_reported = r.split()
        
        num_of_reported[be_reported] += 1
        user_list_who_i_report[do_report].add(be_reported)
        
        if num_of_reported[be_reported] == k:
            suspended.append(be_reported)

    for s in suspended:
        for i in range(len(id_list)):
            if s in user_list_who_i_report[id_list[i]]:
                answer[i] += 1

    return answer

 

Dictionary, defaultdict

문제를 읽고 나서, dictionary 자료구조를 사용해야겠다는 생각은 바로 들었다. 나는 dictionary를 사용해야 하는 문제에서 웬만하면 defaultdict를 사용하려고 하는 편이다.

Defaultdict는 value의 타입만 지정해준다면 key에 매핑되는 값을 하나하나 지정해주지 않아도 자동으로 기본값이 들어가있다.

 

문제를 해결하는데 필요한 dictionary는 2개 정도로 생각되었다.
유저별로 신고한 아이디 정보를 담고 있는 사전(dictionary) 1개,
각 유저별로 신고당한 횟수 정보를 담고 있는 사전 1개.
해당 사전들은 다음과 같은 key : value로 구성했다.

• 신고를 행한 유저 A(string) : 유저 A가 신고한 유저 목록(set)
  user_list_who_i_report
• 신고를 당한 유저 A(string) : 유저 A가 신고당한 횟수(int)
  num_of_reported

이렇게 주어진 정보들을 정리할 사전을 마련해놓고, 이 정보들을 이용하여 문제에서 요구하는 조건에 따라 정답을 이끌어내보자.

문제조건 및 제한사항

이 문제에서는 k(주어지는 숫자)번 이상 신고당한 유저는 게시판 이용이 정지되고, 해당 유저(정지당하는 유저)를 신고한 유저에게 처리 결과 메일을 발송한다. 따라서 신고당한 유저와 그 횟수 정보를 저장한 사전과 별개로, 그 중 k번 이상 신고당한 유저의 목록을 따로 가지고 있는게 좋겠다.
이를 위해 만든 리스트가 suspended 이다.

또한 제한사항에서 return하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으라고 했다. 이를 수행하기 위해 코드 초반에 answer를 아예 [0, 0, 0, 0]과 같이 초기화시켰다.(id_list의 len 만큼만)

report 중복 제거

딕셔너리와 간단한 반복문을 이용하여 풀어낸 나의 첫 번째 시도는 시간초과 무덤에 빠져버렸다. 살짝(구라) 당황했지만 침착하게 문제를 다시 읽어보았다. 문제 설명의 가장 첫 부분에서 내 실수를 찾을 수 있었다.

"한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다."

입출력 예 두 번째 항목의 report = ["ryan con", "ryan con", "ryan con", "ryan con"] 처럼 같은 값이 여러 번 반복이 되어도, 결국 ryan이 con을 신고한 횟수는 1회로 처리된다.

따라서 최대 길이 200,000인 report를 최대한 줄여주는 것, 즉 중복된 값을 제거해주는 것을 통해 시간 초과 문제를 해결할 수 있었다.

report = set(report)

나는 set으로 형변환해주는 작업을 통해 해결하였다.

해결

주어진 리스트 report에 들어있는 값은 "신고하는사람 신고당하는사람" 형태로 되어있기 때문에, 각 데이터를 split() 함수를 이용하여 공백을 기준으로 나눠주고, 신고한 사람을 do_report로, 신고당한 사람을 be_reported로 정의하여 값을 얻었다.

이 상태에서 반복문 및 조건문을 이용하여 위에 정의한 두 딕셔너리를 채워주고, 채움과 동시에 k번 이상 신고당해 게시판 이용이 정지된 유저도 걸러낼 수 있었다.

num_of_reported 사전에 유저 별 신고당한 횟수를 기록할 때, 신고당해서 1을 더하여 k가 된다면 앞으로 몇 번 더 신고당하던지 정지 대상자이므로 suspended에 담아주면 된다.

마지막으로 각 유저들이 신고한 내용(사람)이 담겨있는 딕셔너리(user_list_who_i_report)와 id_list를 이용하여 suspended에 속한 유저들이 user_list_who_i_report[id_listr[i]]에 포함되어 있다면 answer에서 해당되는 자리(반복문 & 인덱스 접근이므로 순서가 자연히 맞는다)의 수를 1 증가시키는 것으로 이 문제를 해결할 수 있다.

 

후기

처음풀어보는 카카오 코딩테스트였는데, 1번이라 그런지 난이도가 쉬웠다.

이 기세로 코딩테스트 문제를 다 풀어보도록 하자.