Programmers School level 1: 신고 결과 받기

<풀기 전 생각>

문자열을 찾아야 하므로 indexOf() contains() matches() 이 세 개의 메소드를 생각할 수 있었고
또 찾은 문자열을 분리해야 하는데 속도 이슈로 split과 tokenizer를 쓰기보다는 subString()을 써야겠다고 생각을 할 수 있었다. 마지막으로 HashMap을 통해 중복을 제거하면 되겠다고 생각하고 문제 풀이에 들어갔다.

<중간 문제점>

문제를 완벽히 이해하지 못 한 상태로 문제 풀이에 들어가서 중간 중간 코드를 계속 수정하는 일이 빈번하여 확실히 문제를 이해하고 나서 풀이에 들어가야겠다.

<최종코드>

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

class Solution {
    // 시간 복잡도 O(n^2*log n) 공간 복잡도 O(n)
    // 누가 누구들에게 신고 당했는지 알 수 있는 자료구조
    // Set을 쓰는 이유는 contains 함수를 쓰기 위해서
    private HashMap<String, HashSet<String>> whosReported = new HashMap<String, HashSet<String>>();
    // 이름과 배열에 넣을 index 정보를 저장한 Map
    private HashMap<String,Integer> indexMap = new HashMap<String,Integer>();
    // 이름과 신고당한 횟수가 저장된 Map
    private HashMap<String,Integer> map = new HashMap<String,Integer>();

    private void initMap(String[] id_list){
        // for문 보다 속도가 더 빠른 foreach문 사용
        int pos=0;
        for (String name:id_list) {
            map.put(name, 0);
            indexMap.put(name,pos++);
            whosReported.put(name,new HashSet<String>());
        }
    }
    private void reputCount(String[] id_list, String[] report){
        // 문자열 안에서 문자열을 찾는 방법에는 indexOf() contains() matches() 가 있는데
        // 우리는 처음에 나온 index 값을 찾아야 함으로
        // 혹시 유저 이름이 a 와 ab 인 경우는 난감하다 + 다음이 공백인지 아닌지 조건 추가
        // split 과 toknizer를 안쓰는 이유는 속도 때문
        for(int i=0;i<report.length;i++){
            // 처음에 이름이 오는지 체크
            for(int j=0;j<id_list.length;j++){
                int index = report[i].indexOf(id_list[j]);
                // 신고한 유저의 이름이 앞에 나오고 + 그 이름 다음에 공백이 나오는지
                if(index==0&&report[i].charAt(index+id_list[j].length())==' '){
                    String repotedMan = report[i].substring(index+id_list[j].length()+1);
                    HashSet<String> tmp = whosReported.get(repotedMan);
                    // 이미 해당 유저를 신고한 사람이 아니라면
                    if(!tmp.contains(id_list[j])){
                        Integer value = map.get(repotedMan);
                        map.put(repotedMan, value+1);
                        tmp.add(id_list[j]);
                        whosReported.put(repotedMan,tmp);
                    }
                }
            }
        }
    }
    private void mailSend(int[] answer, int k){
        Set<String> set = map.keySet();
        Iterator<String> it = set.iterator();

        while(it.hasNext()){
            String key = it.next();
            int value = map.get(key);
            if(value>=k) {
                // 신고한 사람들에게 제제 되었음을 알리는 메일
                Iterator<String> reputers = whosReported.get(key).iterator();
                // 해당 유저를 제제한 사람들의 목록 가져오기
                while(reputers.hasNext()){
                    String reputer = reputers.next();
                    int index = indexMap.get(reputer);
                    answer[index]++;
                }
            }
        }
    }
    // 총 시간 복잡도 O(n^2 * log n) 공간 복잡도 O(n)
    public int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];
        // 시간 복잡도 O(n) 
        initMap(id_list);
        // 시간 복잡도 O(n^2 * log n)
        reputCount(id_list,report);
        // 시간 복잡도 O(n*m)
        mailSend(answer, k);

        return answer;
    }
}

<메모>

우수 답안을 보니 해당 클래스를 사용하던대 공부 해두어야 할 것 같다. 

import java.util.stream.Collectors;