정답
시간 초과 정답
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을 사용하여 이중 반복이 된 것은 아닌지 의문이 생긴다.