Programmers Lv1 신고 결과 받기

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

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

 

id_list	report	k	result
["muzi", "frodo", "apeach", "neo"]	["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]	2	[2,1,1,0]
["con", "ryan"]	["ryan con", "ryan con", "ryan con", "ryan con"]	3	[0,0]

문제를 요약하자면, id_list의 사람들중에서 신고한 사람이 k번 이상 신고를 받으면 신고한 사람의 수만큼 mail(result)을 받아 그 수를 반환하는 문제였다. 자세한 사항은 문제를 읽어보면 된다.

 

여러 고민과 시도를 해보다 아래 유튜브 강의의 도움을 받아 해결하였다. 

https://www.youtube.com/watch?v=ncCUNOJUn9Q 

---

풀이방식

1. 중복제거

2. notifyListHash 만들기

3. notifyListHash 기반으로 reportHash 만들기

4. reportHash 기반으로 answer 배열 채우기

 

 

유튜브에서는 각 List와 Hash의 구조를 그림으로 그려서 문제를 풀었다.

시각적으로 굉장히 이해하기 쉬웠다. 앞으로 그런 방식으로 해결해보아야겠다.

 

아래 주석을 보면 이해가 쉬울 것이다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

class Main {    
    public int[] solution(String[] id_list, String[] report, int k) {
    
        int[] answer = new int[id_list.length];

        //1. 중복제거
        HashSet<String> reportSet = new HashSet<>();// reportSet이라는 Hashset<String>을 생성
        for(String rep: report) reportSet.add(rep);
        
        //2. notifyListHash 만들기
        HashMap<String, ArrayList<String>> notifyListHash = new HashMap<>();
        for(String rep : reportSet){
            int blankIdx = rep.indexOf(" ");//공백의 위치 int로 반환
            String reporter = rep.substring(0, blankIdx); //신고한 사람
            String reportee = rep.substring(blankIdx+1);//신고당한 사람

            ArrayList<String> reporterList = notifyListHash.getOrDefault(reportee, null); //신고당한 사람이 있으면 reportee반환, 없다면 null 반환

            if(reporterList == null) reporterList = new ArrayList<>(); //아직 신고를 안당해  null이라면, reporterList 생성
            
            reporterList.add(reporter); //reporterList에 reporter 추가
            notifyListHash.put(reportee, reporterList); //notifyListHash에 추가
        }
    
        //3. notifyListHash 기반으로 reportHash 만들기
        HashMap<String, Integer> reporterHash = new HashMap<>();
        for(ArrayList<String> notifyList : notifyListHash.values()){
            if(notifyList.size()>=k){
                for(String reporter : notifyList){ //신고한 사람들 한명씩 전달
                    reporterHash.put(reporter, reporterHash.getOrDefault(reporter, 0)+1);//기존 reporter의 value 값을 반환하고, 값이 없으면 0전달(뒤에 +1, 하나 더 누적) 
                }
            }
        }

        //4. reportHash 기반으로 answer 배열 채우기
        for(int i=0;i<id_list.length;i++){
            answer[i] = reporterHash.getOrDefault(id_list[i], 0);
        }

        return answer;
    }

---

배운점

1. HashSet

HashSet은 Set 인터페이스의 구현 클래스입니다. 그렇기에 Set의 성질을 그대로 상속받습니다. Set은 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있습니다. 또한 저장 순서가 유지되지 않습니다. 

Set은 주머니 형태로 되어 있습니다. 비선형 구조이기에 순서가 없으며 그렇기에 인덱스도 존재하지 않습니다

 

2. HashMap

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션입니다. Map 인터페이스를 상속하고 있기에 Map의 성질을 그대로 가지고 있습니다. Map은 키와 값으로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조입니다.

 

3. HashMap.getOrDeafault(Object Key, Integer defaultValue)

찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환한다

 

4. String.substring(x), String.substring(x, y)

String.substring(x), String의 x번째부터 끝까지 반환

String.substring(x ,y), String의 x번째부터 y-1까지 반환