[프로그래머스/92334] 신고 결과 받기
in Study / Coding Test
☑️ 문제
☑️ 풀이
첫 번째 풀이
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
// 1.
Set<String> set = new HashSet<>();
for (String s : report) {
set.add(s);
}
Map<String, Integer> countMap = new HashMap<>();
Map<String, ArrayList<String>> reportMap = new HashMap<>();
// 2.
Iterator iter = set.iterator();
while (iter.hasNext()) {
String[] str = iter.next().toString().split(" ");
countMap.put(str[1], countMap.getOrDefault(str[1], 0) + 1);
if (!reportMap.containsKey(str[0])) {
reportMap.put(str[0], new ArrayList<>());
}
reportMap.get(str[0]).add(str[1]);
}
// 3.
List<String> admittedUser = new ArrayList<>();
for (String s : id_list) {
if (countMap.getOrDefault(s, 0) >= k) {
admittedUser.add(s);
}
}
// 4.
int[] answer = new int[id_list.length];
for (int i = 0; i < id_list.length; i++) {
String id = id_list[i];
if (reportMap.containsKey(id)) {
List<String> nameList = reportMap.get(id);
for (int j = 0; j < admittedUser.size(); j++) {
String name = admittedUser.get(j);
if (nameList.contains(name)) {
answer[i] += 1;
}
}
}
}
return answer;
}
}
- 한 개의 HashSet과 두 개의 HashMap을 사용했다.
Set<String> set: report 중복 체크용Map<String, Integer> countMap: key - 신고를 받은 이용자, value - 신고받은 횟수Map<String, ArrayList<String>> reportMap: key - 이용자, value - 신고한 이용자의 id 모음 ArrayList- HashSet을 사용하여 report의 중복을 체크한다. (중복 신고는 인정되지 않기 때문)
- HashSet을 순회하면서 countMap과 reportMap을 구성한다.
- countMap을 순회하면서 신고로 인정될 id를 따로 admittedUser에 담는다.
- 각 이용자별 메일을 받는 횟수를 체크한다. 1. 먼저 id_list를 순회하면서 reportMap에 id가 있다면 신고한 이용자의 리스트를 가져온다. 2. 신고한 리스트에 admittedUser에 들어있는 id와 일치하는 id가 있다면 answer 배열의 값을 1씩 증가시킨다.
- answer 배열을 리턴한다.
- 시간 복잡도
- HashSet으로 중복 제거 → O(N) (N: report 길이)
- HashMap 구성 → O(N)
- 정지될 id 체크 → O(M) (M: id_list 길이)
- 메일 받는 횟수 체크 → O(M * A * L) (A: AdmittedUser 길이, L: nameList 길이)
- 최종 시간 복잡도 → O(M * A * L)
두 번째 풀이
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
Set<String> set = new HashSet<>();
for (String s : report) {
set.add(s);
}
Map<String, Integer> countMap = new HashMap<>();
Map<String, HashSet<String>> reportMap = new HashMap<>();
Iterator iter = set.iterator();
while (iter.hasNext()) {
String[] str = iter.next().toString().split(" ");
countMap.put(str[1], countMap.getOrDefault(str[1], 0) + 1);
if (!reportMap.containsKey(str[0])) {
reportMap.put(str[0], new HashSet<String>());
}
reportMap.get(str[0]).add(str[1]);
}
List<String> admittedUser = new ArrayList<>();
for (String s : id_list) {
if (countMap.getOrDefault(s, 0) >= k) {
admittedUser.add(s);
}
}
int[] answer = new int[id_list.length];
for (int i = 0; i < id_list.length; i++) {
String id = id_list[i];
if (reportMap.containsKey(id)) {
HashSet<String> nameSet = reportMap.get(id);
for (int j = 0; j < admittedUser.size(); j++) {
String name = admittedUser.get(j);
if (nameSet.contains(name)) {
answer[i] += 1;
}
}
}
}
return answer;
}
}
- 첫 번째 풀이에서는 reportMap의 Value로 ArrayList를 사용했고,
ArrayList.contains()를 사용해 선형 탐색을 했기때문에 시간 복잡도가 컸다. - ArrayList를 대신해서 HashSet을 사용하면
HashSet.contains()사용 시 시간복잡도가 O(1)이 되어 최종 시간복잡도가 O(N^2)으로 줄어든다.
세 번째 풀이
import java.util.*;
class Solution {
public int[] solution(String[] id_list, String[] report, int k) {
Map<String, HashSet<String>> reportMap = new HashMap<>();
Map<String, Integer> countMap = new HashMap<>();
for (String r : report) {
String[] reportStr = r.split(" ");
if (!reportMap.containsKey(reportStr[1])) {
reportMap.put(reportStr[1], new HashSet<>());
}
reportMap.get(reportStr[1]).add(reportStr[0]);
}
for (int i = 0; i < id_list.length; i++) {
if (reportMap.containsKey(id_list[i])) {
HashSet<String> userSet = reportMap.get(id_list[i]);
if (userSet.size() >= k) {
Iterator iter = userSet.iterator();
while (iter.hasNext()) {
String name = iter.next().toString();
countMap.put(name, countMap.getOrDefault(name, 0) + 1);
}
}
}
}
int[] answer = new int[id_list.length];
for (int i = 0; i < id_list.length; i++) {
answer[i] = countMap.getOrDefault(id_list[i], 0);
}
return answer;
}
}
- 책의 풀이를 참고했다.
- 앞의 풀이와 다른 점은
Map<String, HashSet<String>> reportMap: key - 신고를 당한 이용자, value - 신고한 이용자의 HashSetMap<String, Integer> countMap: key - 이용자, value - 메일을 받는 횟수- reportMap의 value로 HashSet을 사용했기 때문에 따로 report 중복 체크를 해줄 필요가 없어졌다.
- reportMap의 HashSet의 크기가 k보다 크거나 같다면 해당 이용자는 신고 횟수를 충족한다는 점을 이용해 해당 HashSet을 순회하면서 countMap을 완성하였다.
- 시간복잡도
- report를 순회하면서 reportMap 완성 → O(N) (N: report 길이)
- id_list을 순회하면서 reportMap의 HashSet 찾음, HashSet 순회하면서 countMap 완성 → O(M^2) (M: id_list 길이)
- id_list 순회하면서 answer 배열 완성 → O(M)
- 최종 시간복잡도 → O(N + M^2)
