[알고리즘] 신고 결과 받기

문제

문제 설명

• 게시판 사용 유저는 서로 다른 유저를 횟수 제한 없이 신고 할 수 있다.
• 한 유저를 여러번 신고 할 수 있지만, 동일 유저의 신고는 1회로 처리된다.
• k번 이상 신고 당한 유저는 게시판 이용이 정지된다.
• 내가 신고한 유저가 정지를 당할 경우 해당 유저가 정지당했다는 메일이 나에게 온다.
• 전체 유저목록과 유저가 신고한 ID목록, 정지 기준 k 가 주어진다.
• 이 때, 각 유저별로 메일을 받는 횟수를 구하라

제한 사항

• 전체 유저목록은 중복이 없다.
• 유저가 신고한 ID목록은 "신고자 신고당한자" 형태이다. (신고자가 신고당한자를 신고했다는 의미)
• 자기가 자기 자신을 신고하는 경우는 없다.

문제 풀이

나의 풀이

시간 초과된 풀이

나는 이 문제를 두번을 풀어서야 정답을 맞췄다. 첫번째 시도는 정답은 맞지만 여러 케이스에서 시간초과에 걸렸다.

먼저 실패했던 코드이다.

function getMyReportInfo(id_list, report) {
  let myReportInfo = id_list.map((id) => {
    let myReport_list = [];
    for (let i = 0; i < report.length; i++) {
      //아이디가 같으면서, 중복된것이 없도록 if를 걸었음
      if (
        report[i].split(" ")[0] === id &&
        !myReport_list.includes(report[i].split(" ")[1])
      ) {
        myReport_list.push(report[i].split(" ")[1]);
      }
    }
    return { id, myReport: myReport_list };
  });
  return myReportInfo;
}
function getIsReportedInfo(myReportInfo, id_list, k) {
  let isReportedInfo = id_list.map((id) => {
    // isReported 각 id가 신고당한 횟수
    let isReported;
    let isReportedCnt = 0;
    for (let i = 0; i < myReportInfo.length; i++) {
      for (let j = 0; j < myReportInfo[i].myReport.length; j++) {
        if (myReportInfo[i].myReport[j] === id) {
          isReportedCnt = isReportedCnt + 1;
        }
      }
    }
    if (isReportedCnt >= k) {
      isReported = true;
    } else {
      isReported = false;
    }
    return { id, isReported };
  });
  return isReportedInfo;
}

function getCnt(myReportInfo, isReportedInfo) {
  let cnt = myReportInfo.map((info) => {
    let cnt = 0;
    for (let i = 0; i < isReportedInfo.length; i++) {
      if (
        isReportedInfo[i].isReported === true &&
        info.myReport.includes(isReportedInfo[i].id)
      ) {
        cnt = cnt + 1;
      }
    }
    return cnt;
  });
  return cnt;
}

첫 풀이에서 나는 3가지 함수로 분리하였다. 첫 번째는 각 유저가 신고한 사람을 배열로 만들어주고, 두 번째는 각 유저가 신고 당했는지 여부를 판별하는 함수, 마지막 함수는 각 유저가 받는 이메일 개수를 세는 함수이다.

일단 이 코드를 제출 했을 때, 틀린것은 없고 시간초과만 문제가 되었으니 시간복잡도를 줄여보기로 생각했다. 첫 번째 함수의 경우 map안에서 for문을 사용하여 O(n^2)의 시간 복잡도를 갖는다. 두 번째 함수의 경우 똑같이 O(n*m^2)의 형태인데, 최악의 경우라고 생각한다면 O(n^3)의 무시무시한 복잡도를 갖게 된다. 마지막 함수도 O(n^2)의 형태이다.

나는 최대한 반복문을 겹치지 않게 하여 아래와 같이 수정하였다. 먼저 통과한 케이스 사진이다.

통과된 풀이

//각 유저별 신고한 id 리스트 구하는 함수
function getMyReportInfo(id_list, report) {
  let myReportInfo = {};
  for (let i = 0; i < id_list.length; i++) {
    myReportInfo[id_list[i]] = { myReport: [] };
  }

  for (let i = 0; i < report.length; i++) {
    let [user, reportUser] = report[i].split(" ");
    if (!myReportInfo[user].myReport.includes(reportUser)) {
      myReportInfo[user].myReport.push(reportUser);
    }
  }

  return myReportInfo;
}

// 밴 당한 리스트
function getBanList(id_list, k, myReportInfo) {
  let banList = [];
  for (let i = 0; i < id_list.length; i++) {
    let cnt = 0;
    for (let j = 0; j < id_list.length; j++) {
      if (myReportInfo[id_list[j]].myReport.includes(id_list[i])) {
        cnt++;
      }
    }
    if (cnt >= k) {
      banList.push(id_list[i]);
    }
  }
  return banList;
}

//유저가 신고한 결과를 받는 횟수
function getCnt(id_list, myReportInfo, banList) {
  let cntArr = [];
  for (let i = 0; i < id_list.length; i++) {
    let cnt = 0;
    for (let j = 0; j < myReportInfo[id_list[i]].myReport.length; j++) {
      if (banList.includes(myReportInfo[id_list[i]].myReport[j])) {
        cnt++;
      }
    }
    cntArr.push(cnt);
  }
  return cntArr;
}
function solution(id_list, report, k) {
  let myReportInfo = getMyReportInfo(id_list, report);

  let banList = getBanList(id_list, k, myReportInfo);
  let answer = getCnt(id_list, myReportInfo, banList);
  return answer;
}

이번에는 마지막 함수는 차이가 없지만, 처음과 두번째 함수들의 반복문을 한꺼풀씩 벗겨냈다. 사실 아예 모두 벗겨내고 O(n)의 복잡도를 갖게 하고 싶었는데, 아직 실력이 부족해서인지.. 두 시간을 고민 했지만 이정도 밖에 해내지 못했다.

먼저 반복문을 벗겨낸 아이디어는 반복문을 겹쳐서 사용하지 않고 이어서 사용하는 것이다. 그리고 기존에 map을 이용하여 배열로 만들어 냈던 리턴을 for문만을 사용하여 객체를 리턴하였고 객체이기 때문에 쉽게 해당 값에 접근 및 수정할 수 있어서 반복문을 겹치지 않게 되었다.

이 문제를 풀면서 Map과 Set을 사용했더라면 더 쉽고 간결하게 문제를 풀 수 있었다는 것을 뒤늦게 알았다. 취업준비와 사이드프로젝트, 블로그 수정 등... 바쁘게 지내고 있지만 자바스크립트의 핵심을 먼저 공부해야 겠다는 생각이 든다.