[PCCP] Lv1: 신고 결과 받기(92334) 해설

문제

- 문제 링크: 신고 결과 받기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: report의 길이

- M: id_list의 길이

- split(): O(1)

- report를 순회하는 반복문은 최대 N번 순회하고 문자열 길이가 상수이므로 시간 복잡도는 O(N)

- 신고당한 사람을 해시맵에 저장하거나 업데이트하기 위한 시간 복잡도: O(1)

- 해시맵을 순회하면서 각 신고당한 유저의 신고 횟수를 검사한 다음 그 결과를 count 해시맵에 저장: O(N)

- id_list를 순회하면서 결과를 answer에 저장: O(M)

- 총 시간 복잡도: O(2*N + M)

- 최종 시간 복잡도: O(N + M)

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Solution {

    public int[] solution(String[] id_list, String[] report, int k) {
        // 신고당한 유저 - 신고 유저 집합을 저장할 해시맵
        HashMap<String, HashSet<String>> reportedUser = new HashMap<>();
        // 처리 결과 메일을 받은 유저 - 받은 횟수를 저장할 해시맵
        HashMap<String, Integer> count = new HashMap<>();

        // 신고 기록 순회
        for (String r : report) {
            String[] s = r.split(" ");
            String userId = s[0];
            String reportedId = s[1];

            if (!reportedUser.containsKey(reportedId)) { // 신고당한 기록이 없다면
                reportedUser.put(reportedId, new HashSet<>());
            }
            // 신고한 사람의 아이디를 해시맵의 value인 해시셋에 추가
            reportedUser.get(reportedId).add(userId);
        }

        for (Map.Entry<String, HashSet<String>> entry : reportedUser.entrySet()) {
            if (entry.getValue().size() >= k) { // 정지 기준에 만족하는지 확인
                for (String uid : entry.getValue()) { // 해시셋을 순회하며 count 계산
                    count.put(uid, count.getOrDefault(uid, 0) + 1);
                }
            }
        }

        int[] answer = new int[id_list.length];

        // 각 아이디별 메일을 받은 횟수를 순서대로 정리
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = count.getOrDefault(id_list[i], 0);
        }

        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: report의 길이

- M: id_list의 길이

- split(): O(1)

- report를 순회하는 반복문은 최대 N번 순회하고 문자열 길이가 상수이므로 O(N)

- 신고 당한 사람을 딕셔너리에 저장하거나 업데이트: O(1)

- 딕셔너리를 순회하면서 각 신고당한 유저의 신고 횟수를 검사한 다음 그 결과를 count 딕셔너리에 저장: O(N)

- id_list를 순회하면서 결과를 answre에 저장: O(M)

- 총 시간 복잡도: O(2 * N + M)

def solution(id_list, report, k):
    reported_user = {} # 신고당한 유저 - 신고 유자 집합을 저장할 딕셔너리
    count = {} # 처리 결과 메일을 받은 유저 - 받은 횟수를 저장할 딕셔너리
    # 신고 기록 순위
    for r in report:
        user_id, reported_id = r.split()
        if reported_id not in reported_user: # 신고당한 기록이 없다면
            reported_user[reported_id] = set()
        reported_user[reported_id].add(user_id) # 신고한 사람의 아이디를 집합에 담아 딕셔너리에 연결
        
    for reported_id, user_id_lst in reported_user.items():
        if len(user_id_lst) >= k: # 정지 기준에 만족하는지 확인
            for uid in user_id_lst: # 딕셔너리를 순회하며 count 계산
                if uid not in count:
                    count[uid] = 1
                else:
                    count[uid] += 1
    answer = []
    for i in range(len(id_list)): # 각 아이디별 메ㅣㅇㄹ을 받은 횟수를 순서대로 정리
        if id_list[i] not in count:
            answer.append(0)
        else:
            answer.append(count[id_list[i]])
    
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: report의 길이

- M: id_list의 길이

- split() 시간복잡도: O(1)

- report를 순회하는 반복문은 최대 N번 순회하고, 문자열의 길이가 상수이므로 시간복잡도: O(N)

- 신고당한 사람을 오브젝트에 저장하거나 업데이트하기 위한 시간복잡도: O(1)

- 오브젝트를 순회하면서 각 신고당한 유저의 신고 횟수를 검사하고 결과를 count 오브젝트에 저장: O(N)

- id_list를 순회하면서 결과를 answer에 저장: O(M)

- 총 연산: O(2*N + M)

- 최종 시간 복잡도: O(N + M)

function solution(id_list, report, k) {
    const reportedUser = {}; // 신고당한 유저 - 신고 유저 집합을 저장할 오브젝트
    const count = {}; // 처리 결과 메일을 받은 유저 - 받은 횟수를 저장할 오브젝트

    // 신고 기록 순회
    for (const r of report) {
        const [userId, reportedId] = r.split(' ');
        if (reportedUser[reportedId] === undefined) { // 신고당한 기록이 없다면
            reportedUser[reportedId] = new Set();
        }
        reportedUser[reportedId].add(userId); // 신고한 사람의 아이디를 집합에 담아 오브젝트에 연결
    }
    
    // 신고당한 유저별로 신고당한 횟수를 확인
    for (const reportedId of Object.keys(reportedUser)) {
        if (reportedUser[reportedId].size >= k) { // 정지 기준에 만족하는지 확인
            for (const uid of reportedUser[reportedId]) {
                count[uid] = (count[uid] || 0) + 1;
            }
        }
    }
    
    const answer = [];
    
    // 각 아이디별 메일을 받은 횟수를 순서대로 정리
    for (let i = 0; i < id_list.length; ++i) {
        answer.push(count[id_list[i]] || 0);
    }
    
    return answer;
}

solution 2)

import

solution 3)

import