[PCCP] 문자열과 해시함수 [7]

▼ Why ?

HashMap class 사용에 어느정도 익숙해진 것 같아, 이번엔 이전 문제들처럼 하나의 HashMap 객체를 생성해서 해결하는 것이 아닌 좀 더 난이도가 있는 문제를 풀어보려고 한다.

---

▼ 신고 결과 받기

 

문제 정보

신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.

• 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
  
  • 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
  • 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.
• k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
  • 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.

각 유저별로 신고당한 횟수는 다음과 같습니다.

위 예시에서는 2번 이상 신고당한 "frodo"와 "neo"의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.

따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다.

이용자의 ID가 담긴 문자열 배열 id_list, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report, 정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

코딩테스트 연습 - 신고 결과 받기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

제한 사항

• 2 ≤ id_list의 길이 ≤ 1,000
  • 1 ≤ id_list의 원소 길이 ≤ 10
  • id_list의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.
  • id_list에는 같은 아이디가 중복해서 들어있지 않습니다.
• 1 ≤ report의 길이 ≤ 200,000
  • 3 ≤ report의 원소 길이 ≤ 21
  • report의 원소는 "이용자id 신고한id"형태의 문자열입니다.
  • 예를 들어 "muzi frodo"의 경우 "muzi"가 "frodo"를 신고했다는 의미입니다.
  • id는 알파벳 소문자로만 이루어져 있습니다.
  • 이용자id와 신고한id는 공백(스페이스)하나로 구분되어 있습니다.
  • 자기 자신을 신고하는 경우는 없습니다.
• 1 ≤ k ≤ 200, k는 자연수입니다.
• return 하는 배열은 id_list에 담긴 id 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

 

입출력 예

 

어떻게 해결해야 할까?

1. 누가 누구를 신고했는지 먼저 체크해주고, 유저마다 신고당한 횟수를 저장한다
2. 그리고 누가 누구를 신고했는지 체크했던 것을 기반으로, 유저별로 신고한 사람을 확인해 해당 사람이 정지된 유저라면 해당 유저에 해당하는 index에 1씩 더해주면 해결할 수 있을 것 같다
3. 이러한 과정으로 코드를 구현해나가면 될 것 같고, 좀 더 자세히 구상을 해보자
4. 일단 누가 누구를 신고했는지 담을 객체가 필요한데, 동일한 유저를 여러 번 신고할 수 있지만 이 경우엔 해당 유저에 대한 신고 횟수는 1회로 처리된다.
5. 따라서, String 배열인 report에 담긴 요소를 저장할 때, 문자열 내용이 같은 경우엔 중복 처리를 하지 않고 담는 Set interface의 HashSet 객체 'reportSet'를 생성하여 저장해준다
6. 그렇게 저장한 'reportSet'에서 값을 하나씩 읽어올 때 신고한 사람과 신소한 대상을 분리하기 위해 ' String.split() ' 메서드를 사용한다
7. 그렇게 분리한 후, 신고를 한 사람은 key 값으로,  신고한 대상으로 여러명을 저장하기 위해 ArrayList를 타입으로 하는 value 값을 갖는 HashMap 객체 'reporterTarget'를 생성하고 값을 'putIfAbsent()' 메서드를 이용해서 저장한다
8. 이와 동시에 신고당한 사람을 key 값으로, 신고당한 횟수를 value 값으로 하는 HashMap 객체 'reportedCount'도 생성하여 값을 'put' 메서드를 이용해서 저장해준다
9. 결과값을 담을 배열 'answer'를 유저 아이디가 담긴 배열 'id_list' 크기로 생성하자
10. 마지막으로, 'reporterTarget'에서 'id_list'에 요소를 key 값으로 대입해 매칭되는 value 값, 즉 신고한 사람이 정지된 유저인지 체크하고 맞으면 'answer[유저에 해당되는 index]'  값에 1씩 더해 저장해준다

 

해결 코드 0

• for문에서 ' reporterTarget '로부터 받아온 null 값(' target = null ')으로 HashMap class의 instance인 ' reportedCount '에 ' reportedCount.get(target) '처럼 접근하려 해서 NullPointerException이 발생
  
  ➜ 접근하기 전에 null 값인지 먼저 체크하도록 했다
  
  
• HashSet 타입의 ' reportSet '에 값을 저장할 때 for문으로 일일히 저장해줬는데,
  Arrays class의 ' asList() '를 사용해서 배열을 List, 즉 Collection 객체로 변환하여 HashSet 생성자의 매개변수에 넣어주면, List의 데이터를 for문 없이 손쉽게 HashSet 객체에 저장할 수 있도록 수정했다

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashSet<String> reportSet = new HashSet<>(Arrays.asList(report));
        
        /*
        for(String rep : report) {
            reportSet.add(rep);
        }
        */
        
        HashMap<String, ArrayList<String>> reporterTarget = new HashMap<>();
        HashMap<String, Integer> reportedCount = new HashMap<>();
        
        for(String rep : reportSet) {
            String reporter = rep.split(" ")[0];
            String target = rep.split(" ")[1];
            
            reporterTarget.putIfAbsent(reporter, new ArrayList<String>());
            reporterTarget.get(reporter).add(target);
            
            reportedCount.put(target, reportedCount.getOrDefault(target, 0) + 1);
        }
        
        int[] answer = new int[id_list.length];
        
        for(int i = 0 ; i < id_list.length; i++) {
            int mail = 0;
            
            if(reporterTarget.get(id_list[i]) == null) continue;
            
            for(String target : reporterTarget.get(id_list[i]))
                if(reportedCount.get(target) >= k) mail++;
            
            answer[i] = mail;
        }
        
        return answer;
    }
}

 

해결 코드 1

• 꼭 HashSet을 이용해서 중복 제거를 미리 해줘야 하는지에 대해 계속 생각하다가,
  신고자와 신고대상자를 저장할 HashMap의 key 값을 반대로 신고대상자로, value 값을 신고자로 한다면 HashSet을 이용해서 미리 중복 제거를 해주지 않아도 될 것 같아 코드를 다시 작성해봤다
  ( 신고한 사람의 수를 활용하면 신고 당한 유저가 몇 번 신고 당했는지도 따로 저장할 필요가 없다 )
  
  
• 신고 당한 유저(key)를 신고한 사람(value)을 체크하는 것이기 때문에,
  NPE 발생을 막기 위해 유저(key)가 신고한 유저(value)가 없는지 미리 체크(' if(reporterTarget.get(id_list[i]) == null) continue; ')할 필요도 없다
  
  
• 하지만 String 배열 ' id_list ' 에 담긴 유저들의 index 순서대로 정지 메일을 보내줘야 하기 때문에, ' id_list '에 담긴 유저들을 key 값으로, 해당 유저의 ' id_list ' 에서의 index를 value 값으로 하는 HashMap 객체를 따로 생성해서 저장해줘야 한다

import java.util.*;

class Solution {
    public int[] solution(String[] id_list, String[] report, int k) {
        HashMap<String, ArrayList<String>> targetReporter = new HashMap<>();
        HashMap<String, Integer> idIndex = new HashMap<>();
        
        for (int i = 0; i < id_list.length; i++) {
            // id_list의 index와 answer의 index를 맞추기 위해
            idIndex.put(id_list[i], i);
        }

        for (String rep : report) {
            String reporter = rep.split(" ")[0];
            String target = rep.split(" ")[1];
            
            targetReporter.putIfAbsent(target, new ArrayList<>());
            
            if (!targetReporter.get(target).contains(reporter))
                // 신고 대상자를 똑같은 사람이 다시 신고하지 않은 경우
                targetReporter.get(target).add(reporter);
        }
        
        int[] answer = new int[id_list.length];
        
        for (String targetId : targetReporter.keySet())
            // keySet()으로 key를 받아왔기 때문에 key 값이 존재하는지 체크할 필요 X
            if (k <= targetReporter.get(targetId).size())
                // 신고 대상자가 받은 신고 횟수가 k번 이상일 경우 
                for (String reporter : targetReporter.get(targetId))
                    // 해당 신고 대상자를 신고한 사람들에게 메일을 보낸다
                    answer[idIndex.get(reporter)]++;
        
        return answer;
    }
}

---

▼ 정리

 

• ' HashSet(Collection<? extends E> c) '처럼 HashSet 생성자에 Collection 객체를 매개변수로 넣어주면, Collection 객체의 데이터를 HashSet에 담을 수 있다는 것을 기억하자
  
  +) ' Arrays.asList() ' 메서드가 배열을 List 객체로 변환시켜주듯이, 코드를 좀 더 간결하게 작성할 수 있도록 배열을 Collection 객체로 변환시켜주는 메서드를 활용해보자
  
  
• Key 값이 존재하는 경우 Map의 Value의 값을 반환하고, Key값이 존재하지 않는 경우 Key와 Value를 Map에 저장하고 Null을 반환하는 'putIfAbsent()' 메서드를 기억해두면 좋을 것 같다
  
  
• HashMap class의 instance에 값이 null인 key 값으로 접근하면, NullPointerException이 발생하기 때문에 항상 value 값에 접근하려는 key 값이 null이 아닌지 먼저 체크해주는 것을 잊지 말자
  ( 혹은, ' containsKey() ' 메서드를 이용해서 해당 key 값이 있는지 확인 )
  
  
• 중복 제거를 하는 방법은 HashSet 말고도 stream의 ' distinct() ' 메서드도 있다
  
  
• 불필요한 객체를 생성한 부분이 있나 찾아보다가, 굳이 HashSet 객체를 생성해 중복 제거를 미리 해주지 않고도 해결할 수 있는 코드도 작성해보았다.
  
  ➜ key - value 에 넣을 값을 반대로 생각하여 해결