[프로그래머스] 신고 결과 받기

1. 문제

---

 

프로그래머스

2. 풀이 과정

---

k번 신고를 당하면 정지를 당하는데 한 유저가 같은 유저를 중복해서 신고할 수는 없다. 

문제의 정답은 각 유저에게 정지 메일을 몇 개씩 보내야하는지이다.

 

문제를 해결하기 위해 크게 4가지 순서로 생각했다.

 

1. 유저별로 몇번 신고를 받았는지

 

2. 누가 정지를 당했는지

 

3. 각 유저가 누구를 신고했는지

 

4. 각 유저의 신고목록에 정지 유저가 들어가는지

---

각각을 구하기 위해 접근한 방식은 다음과 같다.

예시는 문제의 1번 테스트 케이스를 활용했다.

id_list: ["muzi", "frodo", "apeach", "neo"]

report: ["muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi"]

k: 2

 

1. 유저별로 몇번 신고를 받았는지

key를 유저의 id, value를 신고당한 횟수로 한 HashMap 자료구조를 생각했다.

report 배열의 각각의 정보가 [신고한 유저] [신고당한 유저]의 구조로 되어 있는데 [신고당한 유저]를 key로 설정하고 해당 유저가 report에 등장할 때마다 value값을 1증가 시켜줬다. 

 

예시에 대한 그 결과는 다음과 같다.

 

2. 누가 정지를 당했는지

여기서 k 이상 신고를 받은 유저를 별도의 리스트에 저장했다.

 

예시에 대한 결과는 다음과 같다.

 

3. 각 유저가 누구를 신고했는지

이 부분도 HashMap을 생각을 했다.

key는 당연히 유저의 아이디일 것인데 value를 선정하는데 고민이 있었다.

왜냐하면 한 유저가 특정 유저를 여러번 신고할 수 없다는 조건이 있었기 때문이다. 

따라서 나는 고민 끝에 value로 HashSet을 생각했다. 

 

예시에 대한 결과는 다음과 같다.

 

4. 각 유저의 신고목록에 정지 유저가 들어가는지

이제 마지막으로 2에서 구한 정지 유저 목록과 3에서 구한 각 유저의 신고목록을 보고 각 유저가 받을 메일 수를 계산하면 된다. 

 

예시에 대한 결과는 다음과 같다.

 

 

최종답은 [2, 1, 1, 0]이 된다.

3. 내 코드

---

import java.util.*;
class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, Integer> report_cnt = new HashMap<>();
        HashMap<String, HashSet<String>> report_info = new HashMap<>();
        List<String> ban_list = new ArrayList<>();
        int[] answer = new int[id_list.length];
        
        // 1. 유저별 신고당한 횟수와 유저별 신고한 유저 정보 저장
        for(String r: report) {
            String[] report_arr = r.split(" ");
            String from = report_arr[0];
            String to = report_arr[1];
              
            HashSet<String> set = report_info.getOrDefault(from, new HashSet<>());
            // 해당 유저가 신고한적이 없는 회원이면
            if(!set.contains(to)) {
                set.add(to);
                report_info.put(from, set);
                
                report_cnt.put(to, report_cnt.getOrDefault(to, 0) + 1);
            }
        }
        
        // 2. 유저별 신고당한 횟수를 보고 정지 유저 리스트 생성
        for(String r: report_cnt.keySet()) {
            if(report_cnt.get(r) >= k) {
                ban_list.add(r);
            }
        }
        
        // 3. 정지 유저 리스트를 보고 유저별 메일 받을 횟수 계산
        for(int i = 0; i < id_list.length; i++) {
            for(String ban_user: ban_list) {
                
                HashSet<String> set = report_info.get(id_list[i]);
                if(set != null && set.contains(ban_user)) {
                    answer[i]++;
                }
            }
        }
        
        
        return answer;
    }
}

시간 복잡도

• O(N)

마지막 3. 정지 유저 리스트를 보고 유저별 메일 받을 횟수 계산하는 부분에서 for문이 2개라 언뜻보면 O(N^2)으로 오해할 수 있다. 하지만 문제 조건을 보면 id_list의 최대 길이는 1000이기 때문에 최악의 경우에도 O(1,000,000)이다.

이는 report의 최대 길이인 200,000을 5번 순회한 수준이기 때문에

이 코드의 시간복잡도는 O(N)이다. (N: report의 길이)

 

4. 피드백

---

• HashMap의 key, value로 HashMap을 사용할 수 있다. 
  다만 key로 사용하는 경우 key의 고유성을 HashMap의 값으로 판단하는 것이 아닌 HashMap 객체의 참조값으로 판단하기 때문에 주의가 필요하다.