[프로그래머스] 2022 KAKAO BLIND RECRUITMENT 신고 결과 받기 - 자바(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/92334?language=java# 

코딩테스트 연습 - 신고 결과 받기

 

 

문제 해석

불량 이용자를 신고하려고 합니다.

각 유저는 한 번에 한 명의 유저를 신고하는데 신고 횟수에 제한은 없습니다.

한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리합니다.

 

k번 이상 신고된 유저는 게시판 이용이 정지되며, 모든 유저에게 정지 사실을 메일로 보냅니다.

이때 유저별로 메일을 받은 횟수를 반환하는 함수를 작성해야 합니다.

 

문제 풀이 전 설계

id_list의 길이는 최대 1,000

report의 길이는 최대 200,000

 

정확성 테스트는 10초입니다.

O(N^2)으로 짜게 됬을경우에 2억 번의 연산을 하는데 통과할 수 있을지 없을지 잘 모르겠습니다.

 

한 가지 더 생각나는 부분은 HashMap <key, Value>에서 key값을 신고자 Value를 다시 한번 HashSet <String>을 활용한 신고받은 자로 한다면 O(N)으로 해결 가능할 것 같습니다.

 

이후에 k번 이상 신고받은 자들을 신고한 사람들에게는 정지 사실을 메일로 보내야 합니다.

 

코드

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
    
        int[] answer = new int[id_list.length];
        Map<String, Set<String>> reportedMap = new HashMap<String, Set<String>>();
        Map<String, Integer> reportedCountMap = new HashMap<String,Integer>();
        
        //초기화
        for(String e : id_list){
            reportedCountMap.put(e,0);
            reportedMap.put(e, new HashSet<String>());
        }
        
        
        StringTokenizer st = null;
        String reporter = null;
        String reported = null;
        
        //신고된 사람들
        for(String e : report){
            st = new StringTokenizer(e, " ");
            reporter = st.nextToken();
            reported = st.nextToken();
            
            //만약 신고자 -> 신고받은사람 존재하지않으면 true -> 신고받은사람의 횟수 +1
            if(reportedMap.get(reporter).add(reported)){
      reportedCountMap.put(reported, reportedCountMap.get(reported) + 1);                      
            }
            
        }
        
        //정지 사실을 메일로 보내기 위한 작업
        for(String e : report){
            st = new StringTokenizer(e," ");
            reporter = st.nextToken();
            reported = st.nextToken();
            //신고당한 횟수가 K이상인 경우만 남기기
            if(reportedCountMap.get(reported) < k){
            reportedMap.get(reporter).remove(reported);
            }
        }
     
        for(int i=0; i < id_list.length; i++){
        answer[i] = reportedMap.get(id_list[i]).size();
        }
        
        
        return answer;
    }
}