[Java] 프로그래머스(level-1) - 신고 결과 받기

상세한 문제 내용은 여기에서 확인 바랍니다.

제한사항

• 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 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.

입출력 예시

Input-1
id_list = [“muzi”, “frodo”, “apeach”, “neo”]
report = [“muzi frodo”,”apeach frodo”,”frodo neo”,”muzi neo”,”apeach muzi”]
k = 2
Output-1
[2,1,1,0]

Input-2
id_list = [“con”, “ryan”]
report = [“ryan con”, “ryan con”, “ryan con”, “ryan con”]
k = 3
Output-2
[0,0]

문제 풀이

---

사용자가 들어있는 배열 id_list과, [신고자 피신고자] 배열인 report에서 k번 이상 신고되어 정지된 피신고자를 신고한 사용자를 구해야 한다.
이를 위해 도출한 아이디어는 아래와 같다.

1. 신고자 신고메일 수신횟수를 담을 LinkedHashMap인 result을 선언하고 id:0으로 초기화한다.
2. 같은 id가 같은 id를 신고하는 건 1번으로 처리한다 -> report를 중복없는 HashSet으로 저장한다.
3. reportSet을 돌며 신고당한자와 신고횟수를 HashMap에 저장한다.
4. reportSet의 신고자:피신고자돌며 reportMap의 피신고자:신고횟수와 비교하여 k이상이면 result에서 신고자 메일 수신횟수를 증가시킨다.

위 아이디어를 코드로 작성해보자.

1번. LinkedHaspMap 초기화

먼저, 신고하여 정지된 사용자마다 메일을 받기 위해 id_list의 순서대로 [id:메일횟수] 형식을 지켜 저장하기 위해 LinkedHashMap을 활용했다.
id_list를 순회하며 LinkedHashMap인 result을 id:0으로 초기화했다.

LinkedHashMap이란?
HashMap을 상속받아 만들어졌으며, 순서가 유지되는 HashMap이다.

LinkedHashMap<String, Integer> result = new LinkedHashMap<>();
for(String id : id_list) {
    result.put(id, 0);
}

2번. HashSet을 활용해 중복 신고건 제거

문제 요구사항에서 같은 사용자가 같은 사용자를 신고한 건은 1건으로 처리한다고 하니, report배열의 중복 원소를 제거해야 한다.

HashSet<String> reportSet = new HashSet<>();
for(String s : report) reportSet.add(s);

중복이 허용되지 않는 HashSet에 report배열의 원소를 저장하여 중복을 제거했다.

3번. 피신고자와 신고횟수를 담은 HashMap 생성

피신고자가 몇번 신고를 당했는지, k번 이상 신고당해 정지를 할지 말지를 알기 위해 중복이 제거된 reportSet을 돌며 [피신고자:신고횟수]를 저장한다.

HashMap<String, Integer> reportMap = new HashMap<>();
for(String s : reportSet) {
    String reported = s.split(" ")[1];
    reportMap.put(reported, reportMap.getOrDefault(reported, 0)+1);
}

3번 과정을 통해 reportMap에 저장되는 과정을 보자.

신고자:muzi, 피신고자: frodo -> reportMap=[frodo:1]
신고자:apeach, 피신고자: frodo -> reportMap=[frodo:2]
신고자:frodo, 피신고자: neo -> reportMap=[frodo:2, neo:1]
신고자:muzi, 피신고자: neo -> reportMap=[frodo:2, neo:2]
신고자:apeach, 피신고자: muzi -> reportMap=[frodo:2, neo:2, muzi:1]

4번. 신고자가 받을 메일횟수 구하기

마지막으로, 정지된 사용자를 신고한 신고자가 받을 메일의 횟수를 구하면 된다.
reportSet의 신고자(reporter)가 신고한 피신고자(reported)와 reportMap의 key(피신고자)가 같다면, k번 이상 신고되어 정지되었는지 확인한다.
그리고 정지된 사용자라면 맨 처음 작성한 result에서 해당 신고자를 찾아 메일횟수 1을 증가시킨다.

for(String s : reportSet) {
    String reporter = s.split(" ")[0];
    String reported = s.split(" ")[1];
    for(Map.Entry<String, Integer> entry : reportMap.entrySet()) {
        if(reported.equals(entry.getKey()) && entry.getValue()>=k) result.put(reporter, result.getOrDefault(reporter, 0)+1);
    }
}

4번 과정을 통해 result에 변경점을 알아보면,

reportMap=[frodo:2, neo:2, muzi:1]

신고자:muzi, 피신고자: frodo -> frodo는 정지된 사용자로 muzi에게 메일을 전송한다. -> result=[muzi:1,frodo:0, apeach:0, neo:0]
신고자:apeach, 피신고자: frodo -> frodo는 정지된 사용자로 apeach에게 메일을 전송한다. -> result=[muzi:1,frodo:0, apeach:1, neo:0]
신고자:frodo, 피신고자: neo -> neo는 정지된 사용자로 frodo에게 메일을 전송한다. -> result=[muzi:1,frodo:1, apeach:1, neo:0]
신고자:muzi, 피신고자: neo -> neo는 정지된 사용자로 muzi에게 메일을 전송한다. -> result=[muzi:2,frodo:1, apeach:1, neo:0]
신고자:apeach, 피신고자: muzi -> muzi는 1번 신고되어 정지되지 않았기에 apeach에게 메일을 전송하지 않는다. -> result=[muzi:2,frodo:1, apeach:1, neo:0]

이렇게 작성한 코드를 제출하니 모든 테스트케이스를 정상적으로 통과하였다.

작성 코드

---

import java.util.*;

class Solution {
    public static void main(String[] args) {
        String[] id_list = {"muzi", "frodo", "apeach", "neo"};
        String[] report = {"muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"};
        // String[] id_list = {"con", "ryan"};
        // String[] report = {"ryan con", "ryan con", "ryan con", "ryan con"};
        int k=2;

        long start = System.currentTimeMillis();
        solution(id_list, report, k);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int[] solution(String[] id_list, String[] report, int k) {
        // 1. 아이디어 
        // 1.1 신고자 신고메일 수신횟수를 담을 LinkedHashMap인 result을 선언하고 id:0으로 초기화한다.
        // 1.2 같은 id가 같은 id를 신고하는 건 1번으로 처리한다 -> report를 중복없는 HashSet으로 저장한다.
        // 1.3 reportSet을 돌며 신고당한자와 신고횟수를 HashMap에 저장한다.
        // 1.4 reportSet의 신고자:피신고자돌며 reportMap의 피신고자:신고횟수와 비교하여 k이상이면 result에서 신고자 메일 수신횟수를 증가시킨다.
        LinkedHashMap<String, Integer> result = new LinkedHashMap<>();
        for(String id : id_list) {
            result.put(id, 0);
        }

        HashSet<String> reportSet = new HashSet<>();
        for(String s : report) reportSet.add(s);

        HashMap<String, Integer> reportMap = new HashMap<>();
        for(String s : reportSet) {
            String reported = s.split(" ")[1];
            reportMap.put(reported, reportMap.getOrDefault(reported, 0)+1);
        }

        for(String s : reportSet) {
            String reporter = s.split(" ")[0];
            String reported = s.split(" ")[1];
            for(Map.Entry<String, Integer> entry : reportMap.entrySet()) {
                if(reported.equals(entry.getKey()) && entry.getValue()>=k) result.put(reporter, result.getOrDefault(reporter, 0)+1);
            }
        }

        int[] answer = new int[id_list.length];
        int idx = 0;
        for(int cnt : result.values()) {
            answer[idx] = cnt;
            idx++;
        }
        
        return answer;
    }
}

회고

• LinkedHashMap, HashMap을 활용하여 [key,value] 대로 접근하는 방법을 제대로 복습하고 익힐 수 있었다.
• 드디어 프로그래머스 레벨 1 문제들을 모두 풀었다. 레벨 2 문제들도 같이 병행하여 풀고있었는데, 코딩테스트까지 남은 이틀 레벨 2 문제 열심히 풀어야겠다.