[프로그래머스][Lv.1][JAVA][2022 KAKAO BLIND RECRUITMENT]신고 결과 받기
by 빔o0O2024. 4. 3.
문제
신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 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 함수를 완성해주세요.
제한사항
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 순서대로 각 유저가 받은 결과 메일 수를 담으면 됩니다.
(*입출력 예 생략)
분석
맵 구조(rptMap)로 유저ID-신고한유저ID명단(" "구분자)를 담는다. 이 때, 신고한 유저 ID 명단에 담긴 ID는 중복되지 않는다.
맵 구조로(cntMap) 유저ID-신고누적횟수를 담는다.
report 를 순회하여 위의 2개 map을 완성한 후 최종적으로 totMap의 신고횟수가 k를 초과하는 이용정지유저를 구한다.
rptMap 에서 3에서 구한 이용정지유저를 신고한 사람과, 몇 명의 정지유저를 신고했는지 횟수를 int[] 배열에 담아 return한다. => 이걸 한다면 map의 entrySet으로 map을 순회하면서 value가 k 이상인 유저를 구하고, rptMap의 value로 그 유저들이 몇 명이나 담겼는지 확인(아마 indexOf를 쓰지 않을까).
아니, 차라리 rptMap 을 순회하면서 value에 들어간 ID 중 몇 개가 이용정지됐는지를 구하는 게 빠르려나. => 이렇게 한다면 rptMap을 for로 돌고, value를 String.split(" ") 으로 분리하고 그걸 다시 for로 순회하면서 map.get() 으로 그것들의 횟수를 구한다. => 이렇게 하면 신고횟수가 충족되지 않은 유저까지 모두 순회하고 map.get을 수행하게 되어서 시간효율이 그다지 좋을 것 같지 않다...
반례를 통해 검증해보니 특정 아이디가 다른 아이디에 포함된 경우(b) 체크가 제대로 이루어지지 않는 것으로 확인. 구분자 " "도 썼으면서 뭔가 부족하게 썼던 모양. 일단 수정. 하지만 수정했음에도 제대로 되지 않았다...
실패의 이유를 제대로 모르는 채로 그냥 소스자체를 다 갈아엎고 좀 다른 방식으로 가기로 함. 중복 방지를 위해 Set을 썼다는 사람이 꽤 많길래(질문하기 게시판 참고) 나도 그걸 사용하는 방식으로 바꿨다. 다만 결국 set에 contains 값에 따라 분개한 부분이 있어서 이럴 거면 중복처리한 의미가 있나 싶기도 하고. 제출한 답안은 하기 답안 부분 참고.
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
Map<String, String> rptMap = new HashMap(); // ID-신고한ID
Map<String, Integer> cntMap = new HashMap(); // ID-신고당한 횟수
// map 변수를 완성하기 위한 for문
for(String r : report) {
String[] s = r.split(" "); // 인덱스 0 신고자 / 1 피신고자
String val = rptMap.getOrDefault(s[0], ""); // 기존 value
// 1. 피신고자 ID 명단 추가
// 기존에 없던 피신고자라면 값 추가
if(val.indexOf(s[1]) == -1) {
rptMap.put(s[0], val + s[1] + " ");
// 2. 신고당한 횟수 누적
cntMap.put(s[1], cntMap.getOrDefault(s[1], 0) + 1);
}
}
// k 이상으로 신고당한 유저를 List로 담는다.
List<String> banUsers = new ArrayList();
for(Map.Entry<String, Integer> entry : cntMap.entrySet()) {
Integer value = entry.getValue();
if(value >= k) banUsers.add(entry.getKey());
}
// 신고자 중 정지유저 명수 체크 == 메일발송 횟수
for(int i = 0; i < id_list.length; i++) {
String reportedUsers = rptMap.getOrDefault(id_list[i], "");
for(String banUser : banUsers) {
if(reportedUsers.indexOf(banUser) > -1) answer[i] = answer[i] + 1;
}
}
return answer;
}
}
실패한 2회차 코드
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
Map<String, String> rptMap = new HashMap(); // ID-신고한ID
Map<String, Integer> cntMap = new HashMap(); // ID-신고당한 횟수
// map 변수를 완성하기 위한 for문
for(String r : report) {
String[] s = r.split(" "); // 인덱스 0 신고자 / 1 피신고자
String val = rptMap.getOrDefault(s[0], " "); // 기존 value
// 1. 피신고자 ID 명단 추가
// 기존에 없던 피신고자라면 값 추가
if(val.indexOf(" " + s[1] + " ") == -1) {
rptMap.put(s[0], val + s[1] + " ");
// 2. 신고당한 횟수 누적
cntMap.put(s[1], cntMap.getOrDefault(s[1], 0) + 1);
}
}
// k 이상으로 신고당한 유저를 List로 담는다.
List<String> banUsers = new ArrayList();
for(Map.Entry<String, Integer> entry : cntMap.entrySet()) {
Integer value = entry.getValue();
if(value >= k) banUsers.add(entry.getKey());
}
// 신고자 중 정지유저 명수 체크 == 메일발송 횟수
for(int i = 0; i < id_list.length; i++) {
String reportedUsers = rptMap.getOrDefault(id_list[i], "");
for(String banUser : banUsers) {
if(reportedUsers.indexOf(banUser) > -1) answer[i] = answer[i] + 1;
}
}
return answer;
}
}
답안
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
int[] answer = new int[id_list.length];
Map<String, Integer> banCntMap = new HashMap(); // 신고당한 횟수 MAP
Map<String, Set<String>> reportMap = new HashMap(); // 신고한 명단 MAP
// Map 완성 시키기
for(String re : report) {
String[] r = re.split(" ");
Set<String> reportSet = reportMap.getOrDefault(r[0], new HashSet());
if(!reportSet.contains(r[1])) {
banCntMap.put(r[1], banCntMap.getOrDefault(r[1], 0) + 1);
reportSet.add(r[1]);
reportMap.put(r[0], reportSet);
}
}
// k 이상으로 신고당한 유저를 List로 담는다.
List<String> banUsers = new ArrayList();
for(Map.Entry<String, Integer> entry : banCntMap.entrySet()) {
Integer value = entry.getValue();
if(value >= k) banUsers.add(entry.getKey());
}
for(int i = 0; i < id_list.length; i++) {
// 해당 유저가 신고한 명단을 가져온다.
Set<String> reportSet = reportMap.getOrDefault(id_list[i], new HashSet());
for(String banUser : banUsers) {
if(reportSet.contains(banUser)) {
answer[i] = answer[i] + 1;
}
}
}
return answer;
}
}
다른 사람의 답안
// 스트림.....
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
List<String> list = Arrays.stream(report).distinct().collect(Collectors.toList());
HashMap<String, Integer> count = new HashMap<>();
for (String s : list) {
String target = s.split(" ")[1];
count.put(target, count.getOrDefault(target, 0) + 1);
}
return Arrays.stream(id_list).map(_user -> {
final String user = _user;
List<String> reportList = list.stream().filter(s -> s.startsWith(user + " ")).collect(Collectors.toList());
return reportList.stream().filter(s -> count.getOrDefault(s.split(" ")[1], 0) >= k).count();
}).mapToInt(Long::intValue).toArray();
}
}
// 이것이 객체지향이라는 수많은 찬사 댓글이 달린 코드.
// 이것이... 객체지향...?
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<>();
}
}
/*
나랑 key-value를 반대로 한 경우.
나는 신고자-피신고자명단 으로 Map 을 구성했는데,
이 사람은 피신고자-신고자명단 으로 Map을 구성해서 신고자명단 역할을 하는 Set의 size를 구하여
별도의 신고횟수를 카운팅하지 않았음.
그리고 return은 스트림.
*/
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
// key: 신고당한놈, value: 몇명한테 당했는지
Map<String, Set<String>> map = new HashMap<>();
for (String rep : report) {
String[] arr = rep.split(" ");
Set<String> set = map.getOrDefault(arr[1], new HashSet<>());
set.add(arr[0]);
map.put(arr[1], set);
}
// key: 알림받을 놈, value: 몇번 알림받을지
Map<String, Integer> countMap = new LinkedHashMap<>();
for (String id : id_list) {
countMap.put(id, 0);
}
for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
if (entry.getValue().size() >= k) { // 정지당할놈
for (String value : entry.getValue()) {
countMap.put(value, countMap.getOrDefault(value, 0) + 1);
}
}
}
return countMap.values().stream().mapToInt(Integer::intValue).toArray();
}
}
