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

문제

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

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: report의 길이

- report를 순회하고 report_user에 저장하면 시간 복잡도는 O(N)

- M: 두번째 반복문에서 reported_user(신고당한 사용자의 정보)의 길이

- K: 총 처리 결과 메일 발송 횟수

- 두번째 반복문의 시간 복잡도는 O(M*K)

- 맨마지막 반복문은 id_list의 길이만큼 순회하나, 문제 조건을 보면 id_list는 최대 개수가 1,000이므로 상수로 무시

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

#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    // 신고당한 유저 - 신고 유저 셋
    unordered_map<string, unordered_set<string>> reported_user;
    unordered_map<string, int> count; // 처리 결과 메일을 받은 유저 - 받은 횟수
    
    // 신고 기록 순회
    for (string& r : report) {
        // 각 report에서 user_id와 report_id를 분리하고 reported_user에 추가
        stringstream ss(r);
        string user_id, reported_id;
        ss >> user_id >> reported_id;
        reported_user[reported_id].insert(user_id);
    }
    
    for (auto& [reported_id, user_id_lst] : reported_user) {
        if (user_id_lst.size() >= k) { // k명 이상에게 신고당했는지 확인
            for (const string& uid : user_id_lst) { // 각 uid가 신고당한 횟수 기록
                count[uid]++;
            }
        }
    }
    
    vector<int> answer;
    // 아이디별 메일 받은 횟수를 id_list 순서대로 answer에 추가
    for (string& id : id_list) {
        answer.push_back(count[id]);
    }
    
    return answer;
    
}

solution 2)

#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

map<string, int> reportCnt; // 유저별 신고 당한 횟수
map<string, set<string>> reportLog; // 유저별 신고한 타 유저 리스트

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
    vector<int> answer;
    
    for(string s: report) {
        // 문자열 파싱
        int blank = s.find(' ');
        string from = s.substr(0, blank);
        string to = s.substr(blank);
        
        // from -> to 를 신고한 이력이 없다면 반영
        if(reportLog[from].find(to) == reportLog[from].end()) {
            reportCnt[to]++;
            reportLog[from].insert(to);
        }
    }
    
    for(string s: id_list) {
        int res = 0;
        
        // k번 이상 신고 당했다면 결과 메일 +1
        for(string str: reportLog[s])
            if(reportCnt[str] >= k) res++;
        
        answer.push_back(res);
    }
    
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#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<>

 

(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