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

• 문제 링크 : 신고 결과 받기

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

 

정답

 

시간 초과 정답

import java.util.*;
import java.util.stream.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        //유저당 신고한 사람 set 한 list로 가지고 있어야 함.
        //신고된 사람
        //유저가 신고한 사람 setlist와 신고된 사람 카운트 해서 각 index에 맞게 ++

        Set<String> sset = new HashSet<>();
        for(String str: report){
            sset.add(str);
        }
        //set된 신고
        report = sset.stream().toArray(String[]::new);

        //[유저,[신고한 유저들]]
        Map<String, List<String>> ssmap = new HashMap<>();
        for(String str1 :id_list){
            List<String> slist = new ArrayList<>();
            for(String str2 : report){
                String[] ar = str2.split(" ");
                if(str1.equals(ar[0])){
                    slist.add(ar[1]);
                }
            }
            ssmap.put(str1, slist);
        }

        //유저별 신고 카운트
        Map<String, Integer> simap = new HashMap<>();
        for(String str1 : report){
            String[] ar1 = str1.split(" ");
            simap.put(ar1[1], simap.getOrDefault(ar1[1], 0) + 1);
        }

        //신고된 유저들
        List<String> slist = new ArrayList<>();
        for(String str1 : simap.keySet()){
            if(simap.get(str1) >= k){
                slist.add(str1);
            }
        }

        //유저가 신고한 리스트와 신고된 유저들 카운트
        int[] answer = new int[id_list.length];
        int idx = 0;
        for(String str1 : ssmap.keySet()){
            for(int i=0; i<id_list.length; i++){
                if(str1.equals(id_list[i])){
                    idx = i;
                }
            }

            List<String> slist1 = ssmap.get(str1);//유저가 신고한 리스트들
            for(String str2 : slist1){
                if(slist.contains(str2)){
                    answer[idx]++;
                }
            }
        }

        return answer;
    }
}

 

분석

• 정확성 테스트도 중요하지만 효율성 테스트를 통과해야 한다.
• O(N^2)을 O(N)으로 바꾸는게 중요해 보인다.

 

정답 (시간 초과 해결)

import java.util.*;
import java.util.stream.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {

        report = Arrays.stream(report).distinct().toArray(String[]::new);

        Map<String, Integer> siMap = new HashMap<>();
        Map<String, Boolean> sbMap = new HashMap<>();

        for(String str : report){
            String[] arr = str.split(" ");
            siMap.put(arr[1], siMap.getOrDefault(arr[1], 0) +1);

            if(siMap.get(arr[1]) >= k){
                sbMap.put(arr[1], true);
            }
        }

        int len = id_list.length;

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

        int[] a = new int[len];

        for(String str : report){
            String[] arr = str.split(" ");
            if(sbMap.getOrDefault(arr[1], false)){
                a[siMap2.get(arr[0])]++;
            }
        }

        return a;
    }
}

 

분석

• stream을 사용하는데 set을 굳이 한번 더 for문 돌릴 이유가 없어서 distinct()를 추가하였다.
• list를 사용해서 풀면 이중 for문을 사용할 수 밖에 없는 구조이기 때문에 HashMap을 사용하여 O(1)방식을 사용하고
  for문을 사용하여 최종적으로 O(N) 방식으로 해결하였다.

 

참고할 만한 정답

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        List<String> list = Arrays.stream(report).distinct().collect(Collectors.toList());
        HashMap<String, Integer> count = new HashMap<>();
        for (String s : list) {
            String target = s.split(" ")[1];
            count.put(target, count.getOrDefault(target, 0) + 1);
        }

        return Arrays.stream(id_list).map(_user -> {
            final String user = _user;
            List<String> reportList = list.stream().filter(s -> s.startsWith(user + " ")).collect(Collectors.toList());
            return reportList.stream().filter(s -> count.getOrDefault(s.split(" ")[1], 0) >= k).count();
        }).mapToInt(Long::intValue).toArray();
    }
}

 

비교 분석

• 위 코드는 최대한 stream으로 해결한 코드로 보인다.
• Stream을 사용하여 primitive type의 for문 속도 장점은 사라져서 굳이 배열로 변환하지 않고 List를 사용한 것으로 보인다.
• return 부분에서 하나의 스트림으로 처리하려고 한 것 같은데
  stream 내부에 다시 stream을 사용하여 이중 반복이 된 것은 아닌지 의문이 생긴다.