[프로그래머스/Lv.1] 신고 결과 받기 (Java)

신고 결과 받기

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

---

풀이

id -> index 매핑

• 신고 결과 계산할 때 "muzi"같은 문자열 id를 결과 배열 인덱스로 바로 접근해야 함 -> O(1)
• X => 매번 id_list를 탐색해야 함

Map<String, Integer> HM = new HashMap<>();
for (int i = 0; i < n; i++) {
    HM.put(id_list[i], i);
}

 

신고 관계 정리

• 피신고자 -> 자기를 신고한 사람들 집합 => 1번 신고만 인정
• 피신고자(`to`) 
  • X -> 새로운 `HashSet` 생성
  • O -> 기존 `Set` 사용
  • 신고자(`from`)을 `Set`에 추가

Map<String, Set<String>> reportedBy = new HashMap<>();
for (String r : report) {
    String[] str = r.split(" ");
    String from = str[0];
    String to = str[1];

    reportedBy
            .computeIfAbsent(to, key -> new HashSet<>())
            .add(from);
}

 

정지 대상 판별

피신고자 순회 -> 신고자 수 >= k => 정지 대상

• `reportedBy.keySet()`: 신고당한 적 있는 사람들

for (String reportedUser : reportedBy.keySet()) {
    Set<String> reporters = reportedBy.get(reportedUser);

    if (reporters.size() >= k) {
        for (String r : reporters) {
            int idx = HM.get(r);
            result[idx]++;
        }
    }
}

---

예시

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

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

k = 2

 

id -> index 매핑

muzi -> 0 / frodo -> 1 / apeach -> 2 / neo -> 3

 

신고 관계 정리

• frodo -> { muzi, apeach } 
  
  • frodo를 muzi, apeach가 신고
• neo -> { frodo, muzi }
• muzi  ->  { apeach }

 

정지 대상 판별

• frodo -> 신고자 수 2
  • `reportedUser = frodo`
  • `reporters = { muzi, apeach }`
• neo -> 신고자 수 2
• muzi -> 신고자 수 1

---

코드

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        int n = id_list.length;
        int[] result = new int[n];
       
        Map<String, Integer> HM = new HashMap<>();
        for (int i = 0; i < n; i++) {
            HM.put(id_list[i], i);
        }
        
        Map<String, Set<String>> reportedBy = new HashMap<>();
        for (String r : report) {
            String[] str = r.split(" ");
            String from = str[0];
            String to = str[1];
            
            reportedBy
                .computeIfAbsent(to, key -> new HashSet<>())
                .add(from);
        }
        
        for (String reportedUser : reportedBy.keySet()) {
            Set<String> reporters = reportedBy.get(reportedUser);
            
            if (reporters.size() >= k) {
                for (String r : reporters) {
                    int idx = HM.get(r);
                    result[idx]++;
                }
            }
        }
        

        return result; 
    }
}