2022 KAKAO BLIND RECRUITMENT에서 나왔던 문제이며 레벨 1로 분류되어있다.
문제 안에 풀이 과정에 대해 꽤 자세하게 설명되어있다.
1. 각 유저별로 중복을 제외하고 몇번 신고당했는지 체크한다.
2. k번 이상 신고당한 유저는 정지당한다
3. 정지당한 유저를 신고한 친구에게 1점을 준다.(메일을 1개 받는다)
4. id_list의 id 순서대로 점수를 return한다.
<--우선 어떤 방법으로 풀던지 간에
중복신고는 카운트도 되지 않고 메일도 1번만 받기 때문에
처음부터 중복을 제거하고 가면 좋을것같다-->
중복제거? Set이지
const reportSet=[...new Set(report)]
그런데 report 입력 예시를 보니 String으로 되어있어서 신고한id와 신고된id 구분이 안된다.
구분이 스페이스(' ')로 되어있으니 미리 분리까지 해두자
const reportSet = [...new Set(report)].map(v=>v.split(' '))
<--사실 Hash로 풀면 간단할 것 같긴 한데 그냥 for문을 돌려보고싶다-->
const reportSet = [...new Set(report)].map(v=>v.split(' ')) const reportLen = reportSet.length; //배열길이 2번이상 쓸거같으면 그냥 변수화 const idLen = id_list.length let result = new Array(idLen).fill(0) //정답배열 0으로 초기화해주고 for(let i=0;i<idLen;i++){ //id순서대로 for(let j=0;j<reportLen;j++){ //report배열을 돌면서 if(reportSet[j][0]===id_list[i]){ //신고자가 지금의 id면 let count = 0; //신고된 횟수[A] let reported = reportSet[j][1] //신고된놈[B] for(let l=0;l<reportLen;l++){ //신고된놈[B]이 몇번 신고됐는지[A] 체크하려고 또 돈다 if(reportSet[k][1]===reported){ //신고된놈 발견시 신고count++ count++ } if(count>=2){ //k번이상 신고됐으면 result[i]++ //신고한친구에게 점수++ break; //더 count할 필요 없으니 중단 } } } } } return result
하다보니 for문을 3중까지 돌게되었다... 결과는?
우선 테스트케이스 통과
하지만 역시 3중 for문.. 일부 case에서 시간초과가 걸린다 ....
그래도 최대한 줄여보자
const reportSet = [...new Set(report)].map(v=>v.split(' ')) const reportLen = reportSet.length; const idLen = id_list.length let result = new Array(idLen).fill(0) let reportedArr = [] //정지된놈을 저장해서 최대한 반복문을 덜돌려보자 let innocent = [] //정지 안된 친구도 저장해보자 for(let i=0;i<idLen;i++){ for(let j=0;j<reportLen;j++){ if(reportSet[j][0]===id_list[i]){ let count = 0; //신고된횟수(A) let reported = reportSet[j][1] //신고된놈(B) if(reportedArr.includes(reported)){ //신고된놈(B)이 정지된놈에 저장돼있으면 result[i]++ //신고된횟수 셀 필요없이 바로 점수 올려주고 continue; //다음으로 넘어가자 } else if(innocent.includes(reported)){ //신고된놈(B)이 정지안된친구에 저장돼있으면 continue; //바로 패스 } else{ //둘다 아니라면 for(let l=0;l<reportLen;l++){ //세어봐야지 if(reportSet[l][1]===reported){ count++ } if(count>=k){ result[i]++ reportedArr.push(reported) //count가 k가 넘어가면 정지된놈으로 저장 break; } } innocent.push(reported) //다 세어봤는데 k번이 안되면 정지안된친구로 저장 } } } } return result
그 결과는
서버의 고통이 느껴지는 소요시간이지만 그래도 해냈다..
전체 코드
function solution(id_list, report, k) { const reportSet = [...new Set(report)].map(v=>v.split(' ')) const reportLen = reportSet.length; const idLen = id_list.length let result = new Array(idLen).fill(0) let reportedArr = [] let innocent = [] for(let i=0;i<idLen;i++){ for(let j=0;j<reportLen;j++){ if(reportSet[j][0]===id_list[i]){ let count = 0; let reported = reportSet[j][1] if(reportedArr.includes(reported)){ result[i]++ continue; } else if(innocent.includes(reported)){ continue; } else { for(let l=0;l<reportLen;l++){ if(reportSet[l][1]===reported){ count++ } if(count>=k){ result[i]++ reportedArr.push(reported) break; } } innocent.push(reported) } } } } return result }
<--다시 정상으로 돌아와서 Hash로 문제를 풀면 좋겠다는 생각이 들었다.
위에서 반복문으로 카운트했던 신고횟수를 미리 HashMap으로 저장해두고 필요할때 꺼내서 풀어보자-->
const reportSet = [...new Set(report)].map(v=>v.split(' ')) //아이디어1 let reportCount = new Map() for(const report of reportSet){ // 신고내역을 돌면서 reportCount.set(report[1],reportCount.get(report[1])+1||1) // id 나올때마다 신고횟수 추가||신고된적 없으면 1을 set }
아이디별 신고횟수는 구했고 이걸 어떻게 쓸지는 선택사항인듯 하다.
신고관계를 그래프로 표현해서 그래프에서 바로 신고횟수를 이용하여 메일 받는 횟수를 구해도 되고
메일받는 횟수에 대한 HashMap을 하나 더 만들어도 될 것 같은데 후자의 경우로 가보자.
let mail = new Map() for(const report of reportSet){ //신고내역을 돌면서 if(reportCount.get(report[1])>=2){ //신고횟수가 2회 이상이면 mail.set(report[0],mail.get(report[0]+1||1) //신고한사람에게 메일횟수 추가 } }
이후에는 id_list를 돌면서 id순서대로 미리 구해둔 메일횟수를 answer에 넣어주면된다.
let answer = [] for(const id of id_list){ //id_list의 id순서대로 answer.push(mail.get(id)||0) //id에 해댕하는 메일 횟수 answer에 push || 없으면 0 push } return answer
확실히 더 빨라진 결과를 볼 수 있다
전체코드
function solution(id_list, report, k) { const reportSet = [...new Set(report)].map(v=>v.split(' ')) let answer = [] let reportCount = new Map() for(const report of reportSet){ reportCount.set(report[1],reportCount.get(report[1])+1||1) } let mail = new Map() for(const report of reportSet){ if(reportCount.get(report[1])>=k){ mail.set(report[0],mail.get(report[0]+1||1) } } for(const id of id_list){ answer.push(mail.get(id)||0) } return answer }
의외로 입력배열이 짧은경우 반복문 활용한 코드가 시간이 덜걸리는 경우도 있어서 신기했다.
그래도 어떤 횟수같은 데이터를 저장하고 활용하는데는 HashMap이 훨씬 효율적이므로 Hash를 활용하자.