TIL 240611 - 알고리즘 코드카타 리뷰 - 신고 결과 받기

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/92334

프로그래머스

k번 이상 신고당하여 계정정지 메일을 받은 유저를 신고한 유저들에게 처리 결과 메일을 보낸다. 이때 유저별로 처리결과 메일을 받은 횟수를 구하는 문제이다.

 

2. 초기 코드

function solution(id_list, report, k) {
  let blackList = [];
  let mail = id_list.reduce((acc, cur) => {
    acc[cur] = 0;
    return acc;
  }, {});
  let obj = report.reduce((acc, cur, idx, arr) => {
    if (arr.indexOf(cur)!=idx || blackList.includes(cur.split(" ")[1])) {
      return acc;
    }
    cur = cur.split(" ");
    //acc[cur[1]] +=1;
    acc[cur[1]] = acc[cur[1]] ? acc[cur[1]]+1 : 1;
    if (acc[cur[1]]>=k) {
      blackList.push(cur[1]);
    }
    return acc;
  }, {});


  report.forEach((cur) => {
    if (blackList.includes(cur.split(" ")[1])) {
      mail[cur.split(" ")[0]] = mail[cur.split(" ")[0]]+1;
    }
  })

  return Object.values(mail);
}

 

신고내역을 순회하여 유저별 신고당한 횟수를 세어 블랙리스트에 집어넣고, 신고내역을 다시 순회하며 블랙리스트에 속한 유저를 신고한 유저를 다시 카운트하는 식이다. 코드가 매우 비효율적이라 시간초과도 많이 되고, 테스트 결과 오답의 비중이 너무 많았다. 아직 반례는 다 찾지 못했으나, 접근법이 뭔가 크게 잘못됐다는걸 깨달음

 

3. 최종 코드

function solution(id_list, report, k) {
  const ans = new Array(id_list.length);
  ans.fill(0) 
  const report_list = {}
    
  id_list.forEach((user)=>{
      report_list[user] = []
  })
  
  report.forEach((user)=>{
      const [user_id, report_id] = user.split(' ')
      if(!report_list[report_id].includes(user_id)){
          report_list[report_id].push(user_id)
      }        
  })
  
  for(const key in report_list){
      if(report_list[key].length >= k){
          report_list[key].forEach((user)=>{
              ans[id_list.indexOf(user)] += 1
          })
      }
  }
  return ans;
}

 

먼저, 전체 user의 수를 길이로 한 ans 배열을 만든다. 전체 유저의 이름을 key로 하고 빈 배열을 value로 하는 객체를 생성한다. 신고받은 사람의 이름을 객체의 key로, 신고한 사람의 이름이 들어간 배열을 객체의 value에 배열로 집어넣는다. 객체의 value의 길이가 k 이상일 경우 value 배열을 순회하며 신고한 유저의 위치에 해당하는 ans 배열 요소에 1씩 더한다.

 

4. 새롭게 알게된 것

알게됐다기 보다는 알고는 있었는데 하도 안써서 까먹고 있던 기능

일정 길이의 배열을 미리 만들 수 있었다. 항상 빈 배열만 만들었어서..

let ans = [];
for (let i=0; i<id_list.length; i++) {
  ans.push(0);
}

//반복문 없이 배열 만들기
const ans = new Array(id_list.length);
ans.fill(0)