프로그래머스 JS [신고 결과 받기]

신고 결과 받기 문제 보기

프로그래머스

---

문제요약

게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템

각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.
신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.
한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.

k번 이상 신고된 유저는 게시판 이용이 정지되며, 

해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.
유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다.

이용자의 ID가 담긴 문자열 배열 id_list
각 이용자가 신고한 이용자의 ID 정보가 담긴 문자열 배열 report
정지 기준이 되는 신고 횟수 k

각 유저별로 처리 결과 메일을 받은 횟수를 배열에 담아 return

"muzi frodo"의 경우 "muzi"가 "frodo"를 신고했다는 의미

---

문제 풀이 (첫번째 제출: 시간초과로 실패함)

1) 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.

function solution(id_list, report, k) {

  let reportSet = new Set(report);

  reportSet = Array.from(reportSet);

[
  'muzi frodo',
  'apeach frodo',
  'frodo neo',
  'muzi neo',
  'apeach muzi'
]  reportSet

2) 메일을 보낼 id 리스트를 만듭니다.

  const willSendIdList = {};

  id_list.forEach((id) => (willSendIdList[id] = 0));

{ muzi: 0, frodo: 0, apeach: 0, neo: 0 } willSendIdList​

3) 신고 받은 횟수를 기록합니다.

  const reportCount = {};

  reportSet.forEach((id) => {

    const reportedId = id.split(" ")[1];

    reportCount[reportedId] ? reportCount[reportedId]++ : (reportCount[reportedId] = 1);

  });

{ frodo: 2, neo: 2, muzi: 1 } reportCount

4) K회 이상 신고받은 id를 기록합니다.

  const reportCountArray = Object.entries(reportCount);

  const filteredReportCountArray = reportCountArray.filter((id) => id[1] >= k);

[ [ 'frodo', 2 ], [ 'neo', 2 ] ] filteredReportCountArray

5) 정지된 아이디를 신고한 ID의 결과를 배열로 만듭니다.

  filteredReportCountArray.forEach((filteredId) => {

    reportSet.forEach((id, index) => {

      if (filteredId[0] === id.split(" ")[1]) {

        willSendIdList[id.split(" ")[0]]++;

      }

    });

  });

  return Object.values(willSendIdList);

[ 2, 1, 1, 0 ] willSendIdList

}

---

테스트 3 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 14 〉	실패 (시간 초과)
테스트 15 〉	통과 (938.04ms, 67.4MB)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	실패 (시간 초과)

실패한 이유 분석

  let reportSet = new Set(report);

set으로 동일한 신고 사항을 제외한 것은 좋았다.

 

하지만,

  filteredReportCountArray.forEach((filteredId) => {

    reportSet.forEach((id, index) => {

      if (filteredId[0] === id.split(" ")[1]) {

        willSendIdList[id.split(" ")[0]]++;

      }

    });

  });

1) 불필요한 split(" ")의 반복과

2) 이중 for문으로 최대 200,000 * 1,000 회의 연산이 실행될 가능성이 있다.(수치는 정확하지 않음)

function solution(id_list, report, k) {
  let reportSet = new Set(report);
  reportSet = Array.from(reportSet);

  const willSendIdList = {};
  id_list.forEach((id) => (willSendIdList[id] = 0));

  const reportCount = {};
  reportSet.forEach((id) => {
    const reportedId = id.split(" ")[1];
    reportCount[reportedId] ? reportCount[reportedId]++ : (reportCount[reportedId] = 1);
  });

  const reportCountArray = Object.entries(reportCount);
  const filteredReportCountArray = reportCountArray.filter((id) => id[1] >= k);

  filteredReportCountArray.forEach((filteredId) => {
    reportSet.forEach((id, index) => {
      if (filteredId[0] === id.split(" ")[1]) {
        willSendIdList[id.split(" ")[0]]++;
      }
    });
  });

  return Object.values(willSendIdList);
}

---

문제 풀이 (성공한 풀이: 불필요한 split, 이중 for문 없애기)

function solution(id_list, report, k) {

  let reportSet = new Set(report);

1) 처음부터 split(" ")으로 나누어 불필요한 문자열 연산 없애기

  reportSet = Array.from(reportSet).map((id) => id.split(" "));

  const willSendId = {};

  id_list.forEach((id) => (willSendId[id] = 0));

  const reportCount = {};

  reportSet.forEach((reportedId) => {

    reportCount[reportedId[1]] ? reportCount[reportedId[1]]++ : (reportCount[reportedId[1]] = 1);

  });

  const reportCountArray = Object.entries(reportCount);

  let filteredReportCountArray = reportCountArray.filter((id) => id[1] >= k);

  filteredReportCountArray = filteredReportCountArray.map((id) => id[0]);

2) 정지된 id를 기록하고, 해당 id들을 신고한 id만을 골라서 남기기 

  const filteredReportSet = reportSet.filter((id) => filteredReportCountArray.includes(id[1])).map((id) => id[0]);

  filteredReportSet.forEach((id) => willSendId[id]++);

  return Object.values(willSendId);

}

solution(["muzi", "frodo", "apeach", "neo"], ["muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi"], 2);

---

테스트 3 〉	통과 (399.45ms, 108MB)
테스트 9 〉	통과 (145.03ms, 67.7MB)
테스트 10 〉	통과 (105.61ms, 64.8MB)
테스트 11 〉	통과 (280.04ms, 104MB)
테스트 14 〉	통과 (123.31ms, 66MB)
테스트 15 〉	통과 (110.21ms, 72.9MB)
테스트 20 〉	통과 (125.75ms, 65.1MB)
테스트 21 〉	통과 (164.95ms, 76MB)

테스트 15 (938.04ms, 67.4MB) => (110.21ms, 72.9MB)

연산에 걸리는 시간을 1/9로 줄였다~

 

function solution(id_list, report, k) {
  let reportSet = new Set(report);
  reportSet = Array.from(reportSet).map((id) => id.split(" "));

  const willSendId = {};
  id_list.forEach((id) => (willSendId[id] = 0));

  const reportCount = {};
  reportSet.forEach((reportedId) => {
    reportCount[reportedId[1]] ? reportCount[reportedId[1]]++ : (reportCount[reportedId[1]] = 1);
  });
  const reportCountArray = Object.entries(reportCount);
  
  const filteredReportCountArray = reportCountArray.filter((id) => id[1] >= k).map((id) => id[0]);
  const filteredReportSet = reportSet.filter((id) => filteredReportCountArray.includes(id[1])).map((id) => id[0]);
  filteredReportSet.forEach((id) => willSendId[id]++);
  
  return Object.values(willSendId);
}