[programmers] 신고 결과 받기

hwstar·2024년 7월 14일

programmers

Algorithm

목록 보기

6/7

2022 KAKAO BLIND RECRUITMENT 문제

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92334

첫번째 Idea

고유한 값에 대응하는 여러 값을 저장해 놓고 해결해야하는 문제로 보였다.

이러한 문제를 해결할때 key-value 구조를 가지는 자료구조인 해시테이블을 사용해봐야겠다고 생각했다.

파이썬의 딕셔너리는 해시테이블 기반 자료구조이고 key는 정수, 문자열, 튜플 등으로 가능하고 value는 여러가지 자료형을 지원한다.

여기에서 Key는 유저 ID를 저장하기 위해 문자열, value는 중복되지 않는 값을 저장해 놓을 수 있는 set를 사용해보았다. (하나의 유저가 여러번 신고한것은 1번 신고한것으로 처리하기 때문이다. )

코드

from collections import defaultdict

def solution(id_list, report, k):
		# 1
    reporter_dict = defaultdict(set)
    reported_dict = defaultdict(set)
    
    for record in report:
        r, d = record.split()
        reporter_dict[r].add(d)
        reported_dict[d].add(r)
    # 2
    stop_list = [id for id, ids in reported_dict.items() if len(ids) >= k]

		# 3
    for reporter_id, ids in reporter_dict.items():
        cnt = 0
        for reported_id in ids:
            if reported_id in stop_list:
                cnt += 1
        reporter_dict[reporter_id] = cnt
    # 4 
    for i, id in enumerate(id_list):
        if id in reporter_dict.keys():
            id_list[i] = reporter_dict[id]
        else:
            id_list[i] = 0
               
    return id_list

코드 흐름

신고한사람을 key, 신고당한 사람을 value (reporter_dict), 신고당한사람을 key, 신고한 사람을 value (reported_dict)로 하는 두 개의 딕셔너리를 선언하고 저장
k번 이상 신고받아 정지받을 사람의 id를 담은 리스트 생성 (stop_list)
유저가 신고한 사람 중 정지받은 사람이 있는지 확인하고 개수 업데이트
id_list의 id 순서에 맞게 정답을 출력하기 위해 3번에 저장해놓은 개수를 id_list로 업데이트

시간복잡도

1은 R (report의 개수)에 영향을 받는다. O(R) ( 1 ≤ report ≤ 200,000 )
2,4는 N (유저 ID 개수)에 영향을 받는다. O(N) ( 2 ≤ id_list ≤ 1,000)

그러나 3번 부분에서 각 유저에 대해 평균적으로 신고한 사람의 수 M에 비례하다.
최악의 경우에도 M < N 이기 때문에 O( N * M )의 시간복잡도를 갖을 수 있다.

두번째 Idea

신고한 사람과 신고당한 사람이 1:1로 대응되기 때문에 2차원 리스트로 할 수는 있겠다고 생각했다.
대신 유저 ID를 인덱스로 매핑할때는 딕셔너리를 사용해야한다.

def solution(id_list, report, k):
		# 1
    length = len(id_list)
    answer = [0] * length
    key_mapping = {id: i for i, id in enumerate(id_list)}
    report_arr = [[0] * length for _ in range(length)]
    
    # 2
    for record in report:
        reporter, reported = map(lambda x: key_mapping[x], record.split())
        report_arr[reporter][reported] = 1

		# 3
    stop_list = []
    for i in range(length):
        cnt = 0
        for j in range(length):
            cnt += report_arr[j][i]
        if cnt >= k:
            stop_list.append(i)

		# 4
    for i in range(length):
        for j in range(length):
            if report_arr[i][j] and j in stop_list:
                answer[i] += 1

    return answer

2차원 리스트 (테스트 케이스)

	muzi	frodo	neo
muzi	0	1	1
frodo	0	0	1
apeach	1	1	0
neo	0	0	0

muzi : 0, frodo : 1, apeach : 2, neo : 3

행 = 신고한 사람, 열 = 신고 당한 사람

코드 흐름

ID를 인덱스로 매핑하고 2차원 리스트를 0으로 초기화한다.
신고한 사람과 당한 사람에 해당하는 2차원 리스트 공간에 1로 설정한다.

(1로 설정하는 이유 : 신고한 사람과 당한 사람은 1:1 이며, 한 사람의 중복 신고 처리가능하기 때문이다.)
신고를 K번 당한 사람을 알기 위해 2차원 리스트의 열의 합이 K이상인 사람의 인덱스를 저장한다.
각 사용자에 대해 자신이 신고한 사람들 중 정지된 사람의 수를 계산한다.

시간 복잡도

2차원 리스트를 생성하고 3번, 4번 을 수행할 때 2차원 리스트를 모두 순회해야 하는 점에서
시간복잡도가 O(N^2)가 나온다.

만약 N의 크기가 커지고 한 사람당 신고한 사람 수의 평균이 적을 수록 불필요한 순회가 늘어나는 점에서 첫 번째 코드보다 시간 차이가 더욱 커질 것이다.

두 가지 해결방법 비교

첫번째

테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.03ms, 10.3MB)
테스트 3 〉 통과 (1268.71ms, 63.7MB)
테스트 4 〉 통과 (0.04ms, 10.2MB)
테스트 5 〉 통과 (0.06ms, 10.1MB)
테스트 6 〉 통과 (1.22ms, 10.6MB)
테스트 7 〉 통과 (2.70ms, 11MB)
테스트 8 〉 통과 (4.96ms, 11.2MB)
테스트 9 〉 통과 (319.87ms, 35.5MB)
테스트 10 〉통과 (66.71ms, 35.5MB)
테스트 11 〉통과 (696.19ms, 63.6MB)
테스트 12 〉통과 (0.49ms, 10.4MB)
테스트 13 〉통과 (0.29ms, 10.3MB)
테스트 14 〉통과 (451.35ms, 29.5MB)
테스트 15 〉통과 (169.95ms, 52MB)
테스트 16 〉통과 (0.37ms, 10.3MB)
테스트 17 〉통과 (0.29ms, 10.3MB)
테스트 18 〉통과 (0.80ms, 10.1MB)
테스트 19 〉통과 (1.47ms, 10.4MB)
테스트 20 〉통과 (448.31ms, 29.4MB)
테스트 21 〉통과 (676.87ms, 51.9MB)
테스트 22 〉통과 (0.01ms, 10.1MB)
테스트 23 〉통과 (0.01ms, 10.4MB)
테스트 24 〉통과 (0.01ms, 10.2MB)

두번째

테스트 1 〉 통과 (0.02ms, 10.2MB)
테스트 2 〉 통과 (0.07ms, 10.4MB)
테스트 3 〉 통과 (1538.76ms, 32.6MB)
테스트 4 〉 통과 (0.07ms, 10.2MB)
테스트 5 〉 통과 (0.11ms, 10.2MB)
테스트 6 〉 통과 (3.08ms, 10.4MB)
테스트 7 〉 통과 (3.89ms, 10.6MB)
테스트 8 〉 통과 (7.17ms, 11MB)
테스트 9 〉 통과 (366.77ms, 19.3MB)
테스트 10 〉통과 (164.52ms, 19.4MB)
테스트 11 〉통과 (843.78ms, 32.6MB)
테스트 12 〉통과 (5.31ms, 10.4MB)
테스트 13 〉통과 (9.55ms, 10.5MB)
테스트 14 〉통과 (582.60ms, 25.2MB)
테스트 15 〉통과 (287.82ms, 32.7MB)
테스트 16 〉통과 (0.51ms, 10.4MB)
테스트 17 〉통과 (4.63ms, 10.4MB)
테스트 18 〉통과 (5.12ms, 10.3MB)
테스트 19 〉통과 (5.73ms, 10.5MB)
테스트 20 〉통과 (537.49ms, 25.3MB)
테스트 21 〉통과 (764.27ms, 32.8MB)
테스트 22 〉통과 (0.01ms, 10.2MB)
테스트 23 〉통과 (0.01ms, 10.3MB)
테스트 24 〉통과 (0.01ms, 10.2MB)