신고 결과 받기

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

문제설명

• 주어진 파라미터: String[] id_list, String[] report, int k
• 반환값: int[]
• 게시판 불량 이용자 신고, 처리 결과 메일 발송
• 한번에 한명 유저 신고, 신고당 1회
• k번 이상 신고된 유저 → 게시판 이용 정지, 신고한 모든 유저에게 정지 사실 발송
• 같은사람 신고해도 1회로 적용 → 중복을 없애야함

풀이방식

1. reports : 중복 제거 필요 (ArrayList, Set)
2. 신고관련 횟수 Map<String, Integer> 필요 → reports를 돌며 신고관련 map 완성
3. reports를 돌며 신고관련 횟수(k) 이상 사람만 answerScore에 저장
4. answer return

코드

(풀이방식 1)

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        
        int[] answer = new int[id_list.length];
        Map<String, Integer> answerScore = new HashMap<>();
        
        // 1. 중복 없애기 
        List<String> reports = new ArrayList<>();
        for(String reportElement : report ){
            if(!reports.contains(reportElement)){
                reports.add(reportElement);
            }
        }
        
        // 2. list를 하나씩 꺼내서 map에 넣기 
        Map<String, Integer> score = new HashMap<>();
        for(String str : reports){
            String name = str.split(" ")[1];
            score.put(name, score.getOrDefault(name, 0) + 1);         
        }
        
        // 3. reports 돌며 이름 확인해서 더하기 
        for(String str : reports){
            String name1 = str.split(" ")[0]; // 신고 한사람 
            String name2 = str.split(" ")[1]; // 신고 당한사람
            
            if(score.get(name2) != null && 
               score.get(name2) >= k){
                answerScore.put(name1, answerScore.getOrDefault(name1, 0) + 1);
            }
        }
        
        for(int i = 0; i < id_list.length; i++){
            if(answerScore.get(id_list[i]) != null ){
                answer[i] = answerScore.get(id_list[i]);   
            }
        }
        
        return answer;
    }
}

→ 중복을 제거하는 부분에서 ArrayList를 사용했더니 시간초과 발생

contains는 순차적으로 찾기 때문에 O(n)의 복잡도 발생 → 최악의 경우 O($n^2$)

report 길이 = $2 * 10^5$ → 2중반복 불가

(풀이방식2) Set 활용

import java.util.*;

public class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        
        int[] answer = new int[id_list.length];
        Map<String, Integer> answerScore = new HashMap<>();
        Set<String> reports = new HashSet<>();

				// 1. 중복제거 
        for(String str : report){
            reports.add(str);
        }
        
        // 2. 신고당한 횟수 저장 
        Map<String, Integer> score = new HashMap<>();
        for(String str : reports){
            String[] parts = str.split(" ");
            String name = parts[1];
            score.put(name, score.getOrDefault(name, 0) + 1);
        }
        
        // 3. 메일 수신 횟수 저장
        for(String str : reports){
            String[] parts = str.split(" ");
            String name1 = parts[0]; // 신고 한 사람
            String name2 = parts[1]; // 신고 당한 사람
            
            if (score.getOrDefault(name2, 0) >= k) {
                answerScore.put(name1, answerScore.getOrDefault(name1, 0) + 1);
            }
        }
        
        // 4. answer 완성 
        for (int i = 0; i < id_list.length; i++) {
            answer[i] = answerScore.getOrDefault(id_list[i], 0);
        }
        
        return answer;
    }
}

---