프로그래머스_JS - 신고 결과 받기

nd098pkc·2022년 6월 6일
0

코딩테스트 준비

목록 보기
1/15

2022 KAKAO BLIND RECRUITMENT에서 나왔던 문제이며 레벨 1로 분류되어있다.

문제

문제 안에 풀이 과정에 대해 꽤 자세하게 설명되어있다.
1. 각 유저별로 중복을 제외하고 몇번 신고당했는지 체크한다.
2. k번 이상 신고당한 유저는 정지당한다
3. 정지당한 유저를 신고한 친구에게 1점을 준다.(메일을 1개 받는다)
4. id_list의 id 순서대로 점수를 return한다.

풀이과정

<입력>

  1. id목록 "id_list"(Array)
  2. report목록 "report"(Array)
  3. 정지기준 신고횟수 "k"(Number)

<아이디어 1>

<--우선 어떤 방법으로 풀던지 간에
중복신고는 카운트도 되지 않고 메일도 1번만 받기 때문에
처음부터 중복을 제거하고 가면 좋을것같다-->

중복제거? Set이지

const reportSet=[...new Set(report)]

그런데 report 입력 예시를 보니 String으로 되어있어서 신고한id와 신고된id 구분이 안된다.
구분이 스페이스(' ')로 되어있으니 미리 분리까지 해두자

const reportSet = [...new Set(report)].map(v=>v.split(' '))

<호기심 1>

<--사실 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
}

<아이디어 2>

<--다시 정상으로 돌아와서 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를 활용하자.

profile
늦게배운 코딩이 무섭다

0개의 댓글