신고 결과 받기

https://programmers.co.kr/learn/courses/30/lessons/92334

첫 풀이

import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, Set<String>> accused = new HashMap<>();
        HashMap<String, Integer> accusedCount = new HashMap<>();
        Set<String> criminalSet = new HashSet<>();

        // 초기화
        for (String id : id_list) {
            Set<String> reportSet = new HashSet<>();
            accused.put(id, reportSet);

            accusedCount.put(id, 0);
        }

        // 신고 내역을 돌면서 신고 횟수 카운트 + 피신고 횟수 초과 체크
        for (String el : report) {
            String[] reportees = el.split(" ");
            String reporter = reportees[0];
            String reportee = reportees[1];
            Set<String> reportersSet = accused.get(reporter);
            if (reportersSet.contains(reportee)) {
                continue;
            }
            reportersSet.add(reportee);
            accusedCount.put(reportee, accusedCount.get(reportee) + 1);
            if (accusedCount.get(reportee) >= k) {
                criminalSet.add(reportee);
            }
        }

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

        // 모든 아이디를 돌면서 신고한 사람이 정지 계정인지 체크
        for (int i = 0; i < id_list.length; i++) {
            String id = id_list[i];
            int cnt = 0;
            Set<String> myReportingIds = accused.get(id);
            for (String reporteeId : myReportingIds) {
                if (criminalSet.contains(reporteeId)) {
                    cnt += 1;
                }
            }
            answer[i] = cnt;
        }

        return answer;
    }
}

마지막 for문으로 인해 O(n^2)가 된다.

두번째 풀이

첫번째 풀이와 비슷한데 accused의 키로 신고자 대신 피신고자를 넣어 신고 내용의 키 값을 반대로 줬다.
이중 for문이 동일하게 있어서 빅O는 동일하지만 count를 따로 셀 필요가 없어서 조금 더 간결하고 상수값만큼 빨라졌다.
코드는 첫번째 풀이와 실행 속도 비교해본다고 첫번째 풀이로 다시 돌려보다가 실수로 날렸다..