코딩테스트/프로그래머스
[신고 결과 받기]
애플쩀
2022. 5. 26. 08:14
문제 설명
신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
- 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
- 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
- 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. -> 중복X
- k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
- 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.
다음은 전체 유저 목록이 ["muzi", "frodo", "apeach", "neo"]이고, k = 2(즉, 2번 이상 신고당하면 이용 정지)인 경우의 예시입니다.
유저 ID유저가 신고한 ID설명
| "muzi" | "frodo" | "muzi"가 "frodo"를 신고했습니다. |
| "apeach" | "frodo" | "apeach"가 "frodo"를 신고했습니다. |
| "frodo" | "neo" | "frodo"가 "neo"를 신고했습니다. |
| "muzi" | "neo" | "muzi"가 "neo"를 신고했습니다. |
| "apeach" | "muzi" | "apeach"가 "muzi"를 신고했습니다. |
각 유저별로 신고당한 횟수는 다음과 같습니다.
유저 ID신고당한 횟수
| "muzi" | 1 |
| "frodo" | 2 |
| "apeach" | 0 |
| "neo" | 2 |
위 예시에서는 2번 이상 신고당한 "frodo"와 "neo"의 게시판 이용이 정지됩니다. 이때, 각 유저별로 신고한 아이디와 정지된 아이디를 정리하면 다음과 같습니다.
유저 ID 유저가 신고한 ID 정지된 ID
| "muzi" | ["frodo", "neo"] | ["frodo", "neo"] |
| "frodo" | ["neo"] | ["neo"] |
| "apeach" | ["muzi", "frodo"] | ["frodo"] |
| "neo" | 없음 | 없음 |
따라서 "muzi"는 처리 결과 메일을 2회, "frodo"와 "apeach"는 각각 처리 결과 메일을 1회 받게 됩니다. ->정지된 id 만큼
이용자의 ID가 담긴 문자열 배열 id_list,
각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report,
정지 기준이 되는 신고 횟수 k가 매개변수로 주어질 때,
각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- 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 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.
입출력 예
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] |
입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
입출력 예 #2
"ryan"이 "con"을 4번 신고했으나, 주어진 조건에 따라 한 유저가 같은 유저를 여러 번 신고한 경우는 신고 횟수 1회로 처리합니다. 따라서 "con"은 1회 신고당했습니다. 3번 이상 신고당한 이용자는 없으며, "con"과 "ryan"은 결과 메일을 받지 않습니다. 따라서 [0, 0]을 return 합니다.
제한시간 안내
- 정확성 테스트 : 10초
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
Map<String, HashSet<String>> map = new HashMap<>();
Map<String, Integer> idxMap = new HashMap<>();
for (int i = 0; i < id_list.length; i++) {
String name = id_list[i];
map.put(name, new HashSet<>());
idxMap.put(name, i);
}
for (String s : report) {
String[] str = s.split(" ");
String from = str[0];
String to = str[1];
map.get(to).add(from);
}
for (int i = 0; i < id_list.length; i++) {
HashSet<String> send = map.get(id_list[i]);
if (send.size() >= k) {
for (String name : send) {
answer[idxMap.get(name)]++;
}
}
}
return answer;
}
}import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
ArrayList<User> users = new ArrayList<>();
HashMap<String,Integer> suspendedList = new HashMap<>(); //<이름>
HashMap<String,Integer> idIdx = new HashMap<String,Integer>(); // <이름, 해당 이름의 User 클래스 idx>
int idx = 0;
for(String name : id_list) {
idIdx.put(name,idx++);
users.add(new User(name));
}
for(String re : report){
String[] str = re.split(" ");
//suspendedCount.put(str[0], suspendedCount.getOrDefault(str[0],0)+1);
users.get( idIdx.get(str[0])).reportList.add(str[1]);
users.get( idIdx.get(str[1])).reportedList.add(str[0]);
}
for(User user : users){
if(user.reportedList.size() >= k)
suspendedList.put(user.name,1);
}
for(User user : users){
for(String nameReport : user.reportList){
if(suspendedList.get(nameReport) != null){
answer[idIdx.get(user.name)]++;
}
}
}
return answer;
}
}
class User{
String name;
HashSet<String> reportList;
HashSet<String> reportedList;
public User(String name){
this.name = name;
reportList = new HashSet<>();
reportedList = new HashSet<>();
}
}
다른풀이
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
// 1. 중복 제거
HashSet<String> reportSet = new HashSet<String>();
for (String rep : report)
reportSet.add(rep);
// 2. report에서 각 사람이 신고당한 횟수를 countHash으로 정의하기
HashMap<String, ArrayList<String>> notifyListHash = new HashMap<>();
for (String rep : reportSet){
int blankIdx = rep.indexOf(" ");
String reporter = rep.substring(0, blankIdx);
String reportee = rep.substring(blankIdx + 1);
ArrayList<String> reporterList = notifyListHash.getOrDefault(reportee, null);
if(reporterList == null) reporterList = new ArrayList<>();
reporterList.add(reporter);
notifyListHash.put(reportee, reporterList);
}
// 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);
// 4. reporterHash 정보를 answer에 옮겨담기
for (int i = 0; i < id_list.length; i++)
answer[i] = reporterHash.getOrDefault(id_list[i], 0);
return answer;
}
public static void main(String[] args){
Solution sol = new Solution();
String[] id_list = {"muzi", "frodo", "apeach", "neo"};
String[] report = {"muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"};
int k = 2;
// String[] id_list = {"con", "ryan"};
// String[] report = {"ryan con", "ryan con", "ryan con", "ryan con"};
// int k = 3;
sol.solution(id_list, report, k);
}
}