2022 카카오 블라인드 채용 코딩테스트 문제가 공개되었다. 알고리즘 문제풀이 연습도 할 겸 문제를 풀어보기로 했다.

문제

문제 바로가기

풀이

코드를 먼저 공개하고, 보면서 설명을 이어나가보자.

소스코드

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에 매핑되는 값을 하나하나 지정해주지 않아도 자동으로 기본값이 들어가있다.

from collections import defaultdict

(원활한 사용을 위해 이 정도는 외워두자..)

문제를 해결하는데 필요한 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 증가시키는 것으로 이 문제를 해결할 수 있다.

후기

솔직히 아주 쉬운 문제였다(프로그래머스 Lv 1). 내 풀이가 100점짜리도 아니다. 그럼에도 이렇게 자세하게(?) 혹은 투머치하게 글을 남기는 이유는, 문제의 난이도에 상관없이 내가 어떤 사고를 했고 어떤 어려움을 거쳐서 문제를 해결했나 글로 남기고 싶어서다. 꾸준히 하다보면 분명 도움이 될 것이라고 생각한다.