신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다.
다음은 전체 유저 목록이 ["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_list
, 각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report
, 정지 기준이 되는 신고 횟수k
가 매개변수로 주어질 때, 각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return 하도록 solution 함수를 완성해주세요.
id_list
의 길이 ≤ 1,000id_list
의 원소 길이 ≤ 10id_list
의 원소는 이용자의 id를 나타내는 문자열이며 알파벳 소문자로만 이루어져 있습니다.id_list
에는 같은 아이디가 중복해서 들어있지 않습니다.report
의 길이 ≤ 200,000report
의 원소 길이 ≤ 21report
의 원소는 "이용자id 신고한id"형태의 문자열입니다. k
≤ 200, k
는 자연수입니다.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] |
나의 처음 풀이는 테스트 케이스도 무난하게 한 번에 통과하고, 실제로 제출했을 때도 무난하게 잘 풀리는 듯 싶었지만 시간 초과가 나는 경우가 몇 개 생겼었다. (정확도 83.3)
function solution(id_list, report, k) {
let reporter = [];
let reported = [];
let report_temp = [];
let noDuplicate = true;
var answer = [];
//각 id별 신고당한 횟수를 기록할 Object
let reportCount = {};
//각 id별 신고당한 횟수를 모두 0으로 초기화
id_list.forEach(id => reportCount[id] = 0);
//각 신고내용마다 신고자와 신고당한 사람을 분리하여 저장
report.forEach(rpt => {
let reporterLength = reporter.length;
report_temp = rpt.split(' ');
let current_reporter = report_temp[0];
let current_reported = report_temp[1];
//똑같은 신고자가 똑같은 사람을 신고했는지 검사
for(let i=0; i<reporterLength; i++) {
if(reporter[i] == current_reporter && reported[i] == current_reported){
noDuplicate = false;
break;
}
}
//똑같은 신고자가 중복으로 같은 사람을 신고하지 않았다면 신고내용 접수
if(noDuplicate) {
reporter.push(current_reporter);
reported.push(current_reported);
//신고당한 횟수 추가
reportCount[current_reported] += 1;
}
//다시 noDuplicate 변수는 true로 설정해준다.
noDuplicate = true;
})
//k번 이상 신고받은 id들을 추려내어 정지id 리스트에 추가합니다.
let stoppedId = [];
id_list.forEach(id => {
if(reportCount[id] >= k) {
stoppedId.push(id);
}
});
//각 (신고자, 신고당한사람) 케이스마다 신고당한사람이 최종적으로 정지까지
//먹었을 경우, 신고자에게 결과 메일을 받을 횟수를 증가시켜준다.
for(const id of id_list) {
let mailCount = 0;
//이 아이디가 다른 유저를 신고한 경우가 없다면, 당연히 0개의 메일을 받는다.
if(reporter.includes(id) == false) {
answer.push(0);
continue;
}
else{
//이 아이디가 다른 유저를 신고한 경우가 있을 때,
//신고된 아이디가 정지 처분 받았을 경우 결과 메일을 받을 횟수 증가시킨다.
let start = reporter.findIndex(reporter => reporter == id);
for(let i = start; i < reporter.length ; i++) {
if(reporter[i] == id) {
if(stoppedId.includes(reported[i])) {
mailCount++;
}
} else continue;
}
answer.push(mailCount);
mailCount = 0;
}
}
return answer;
}
좀 더 빠른 방법으로 풀 수 있는 방법이 없을까 생각하다가 Set
객체를 생각해냈다. Set
객체를 사용하면 중간에 한 유저가 같은 유저를 여러 번 중복 신고한 경우를 따로 걸러주지 않아도 되서 시간이 덜 걸릴 것이라고 생각했다. (Set
은 중복 없는 원소들의 집합이다!!)
그리고 예상대로, 이전 풀이의 중복신고 검사 과정을 없애니까 시간이 훨씬 단축되고 통과할 수 있게 됐다!
function solution(id_list, report, k) {
var answer = new Array(id_list.length);
for(let i=0; i<id_list.length; i++) {
answer[i] = 0;
}
//Set을 사용하면 알아서 중복이 제거되어 저장된다.
var report_record = new Set(report);
//각 id마다 신고당한 횟수를 저장하기 위한 Object 자료
//신고당한 횟수를 모두 0으로 초기화한다.
var report_count = new Object();
id_list.forEach(id => report_count[id] = 0);
//누가, 누구를 신고했는지 저장할 Set 자료
//원소들은 각각 ["누가", "누구를"] 형태의 배열이다.
var report_info = new Set();
var temp;
report_record.forEach(rec => {
temp = rec.split(' ');
report_info.add(temp);
//마지막으로 신고당한 사람의 신고Count를 하나 올려준다.
report_count[temp[1]] += 1;
})
//정지당한 id들을 report_count Object를 살펴보며 저장한다.
var stoppedId = [];
id_list.forEach(id => {
if(report_count[id] >= k) {
stoppedId.push(id);
}
})
//신고해서 정지먹인 사람이 있으면 answer에 +1씩 해준다.
id_list.forEach((id, idx) => {
report_info.forEach(info => {
if(info[0] == id && stoppedId.includes(info[1])) {
answer[idx] += 1;
}
})
})
return answer;
}
Set
을 이용할 것을 고려해 볼 것!Set
도 forEach
문을 쓸 수 있다!Set
에 원소를 추가하고 싶으면 Set.add
를 이용한다.Object
에 동적으로 key
와 value
를 생성하고 싶다면 대괄호[]
로 해결가능하다.Ex) 위의 코드에서 빈 Object에 동적으로 id와 그에 해당하는 value를 생성해주었다.
var report_count = new Object(); id_list.forEach(id => report_count[id] = 0);
Array
에 특정 값이 포함되어 있는지 알고 싶으면 Array.includes()
를 사용하도록 하자.