[프로그래머스] Lv1. 실패율- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 1

출처 : 프로그래머스 - 실패율

문제

제한사항

📌 내가 생각한 풀이

스테이지별로 [실패한사람, 전체인원]을 담아준 후 Dp를 이용하여 다음 전체인원을 수정해준다. 그런 다음 실패율을 배열에 저장후 sort하여 정답을 구하자.

function solution(N, stages) {
    var answer = [];
    let kk = [];
    let people = stages.length;
    //dp 사용하여 스테이지별로 사람 수 만들자.
    let failArr= Array.from(Array(N+2), ()=>Array(2).fill(0))
    stages.sort((a,b)=>a-b);
    for(var i = 0; i<stages.length; i++){
        let stage = stages[i];
        failArr[stage][0]++;
        failArr[stage][1] = people;
    }
    
    for(var k =1; k<=N; k++){
        let failRate = failArr[k][0]/failArr[k][1];
        failArr[k][1] === 0 ? null : failArr[k+1][1] = failArr[k][1] - failArr[k][0] 
        isNaN(failRate) ? answer.push([k,0]) : answer.push([k,failRate])
       
        
    }
    answer.sort((a,b)=>{
        if(a[1] === b[1]){
            return a[0]-b[0]
        }else{
            return b[1]-a[1]
        }
    })
    return answer.map((d)=>d[0])
}

아래 방식도 정답이긴 하지만 filter()를 계속돌아 시간복잡도가 오래걸리는 모습을 확인할 수 있다.

 function solution(N, stages){
     let result = [];
     for(var i =1 ; i<=N; i++){
         let whole = stages.filter((d)=>d>=i).length;
         let current = stages.filter((d)=>d===i).length;
         result.push([i, current/whole])
     }
     result.sort((a,b)=>b[1]-a[1])
     return result.map((d)=>d[0])
 }

📌 느낀점

가장 기본적인 Dp를 사용하여 전체인원을 구하면 되는 방식이었다.