[Programmers] 신고 결과 받기 - Java

문제 

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

프로그래머스

 

풀이

유저끼리 서로 신고를 하는 시스템에서 신고를 받은 사람이 k번 이상일 경우 신고를 한 사람들이 메일을 발송하는데, 각 유저마다 메일을 받는 횟수를 구하는 문제이다.

 

신고가 겹칠 수 있는 가능성이 있으므로, 중복을 고려하지 않아도 되는 집합을 사용하는게 좋다고 생각했다.

 

문자열을 인덱스로 매핑해야하는 과정에서 Map을 사용하는게 유리하다고 생각했다.

 

신고를 받은 사람의 Map을 사용해서 <신고를 받은 유저, 신고를 한 유저의 집합>의 쌍을 저장하면 문제를 해결할 수 있다.

신고를 하는 횟수는 20만번이 최대이므로, O(1000 + 200000)의 시간복잡도를 가진다.

 

1. 신고를 받은 Map을 만든다.

 

2. 신고를 한 유저들을 추출해서, 신고를 받은 유저와, 신고를 한 유저의 집합에 유저를 넣어주고 Map에 다시 기록한다.

 

3. 집합의 유저의 수가 k이상이면 수를 Map에 기록해준다.

 

4. id_list에 매핑되어 있는 Map에 횟수를 복사해준다.

 

소스코드

import java.util.HashSet;
import java.util.HashMap;
import java.util.StringTokenizer;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, HashSet<String>> toMap = new HashMap<>();  
        HashMap<String, Integer> mailMap = new HashMap<>();
        
        StringTokenizer st = null;
        
        for (String s : report) {
            st = new StringTokenizer(s, " ");
            
            String from = st.nextToken();
            String to = st.nextToken();
            
            HashSet<String> set = toMap.getOrDefault(to, new HashSet<>());
            
            set.add(from);
        
            toMap.put(to, set);
        }
        
        for (String key : toMap.keySet()) {
            if (toMap.get(key).size() >= k) {
                for (String id : toMap.get(key)) {
                    mailMap.put(id, mailMap.getOrDefault(id, 0) + 1);
                }
            }
        }
        
        
        int[] answer = new int[id_list.length];
        
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = mailMap.getOrDefault(id_list[i], 0);
        }
        
        return answer;
    }
}

 

실행결과