[프로그래머스] 실패율 (Javascript)

문제

[프로그래머스] 실패율

풀이

문제 정의

N개의 스테이지가 있고 각각의 스테이지는 1~N번의 번호를 갖는다. 그리고 stages배열에는 플레이어가 진행중인 스테이지의 번호가 주어진다. 즉 stages[i]가 4라면 i번째 플레이어는 1~3번 스테이지를 클리어하고 4번 스테이지를 진행중인 것이다. 만약 stages[i] 가 n+1이라면 i번째 플레이어는 모든 스테이지를 클리어한 것이다.

우리는 각각의 스테이지의 실패율을 구해야 한다. 실패율의 정의는 아래와 같다.
실패율 = "스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수" / "스테이지에 도달한 플레이어 수"
스테이지의 도달한 플레이어의 수에는 이미 스테이지를 클리어한 플레이어의 수도 포함된다.
만약 아직 스테이지에 도달한 플레이어가 한 명도 없을 경우 해당 스테이지의 실패율은 0이된다.

모든 스테이지를 실패율이 높은 순으로 출력하고, 만약 실패율이 같다면 스테이지 번호가 작은 순으로 출력하시오.

해결방안

기존의 실패율을 구하는 공식은 아래와 같이 바꿔줄 수 있다.
실패율 = 클리어하지 못한 플레이어의 수 / (클리어한 플레이어의 수 + 클리어하지 못한 플레이어의 수)

따라서 실패율을 구하기 위해서는 "클리어한 플레이어의 수와"와 "클리어하지 못한 플레이어의 수"를 구해야 한다.
따라서 이 둘을 배열로 만들어서 따로 관리를 한다.

const clear = Array(N+2).fill(0); // 클리어한 플레이어의 수
const unClear = Array(N+2).fill(0); // 클리어하지 못한 플레이어의 수

// i번 스테이지는 도전중인 스테이지 
for(let i=0; i<stages.length; i++){
    unClear[stages[i]]++; 
  	// 0~i-1번 스테이지는 클리어한 스테이지
    for(let j=stages[i]-1; j>=1; j--){
      	clear[j]++;
    }
}

배열의 크기를 N+2로 해준 이유는 N+1번에 도달한 플레이어 즉, 모든 스테이지를 클리어한 플레이어도 고려해주기 위함이다.
두 배열에 값을 모두 저장했다면 두 값을 계산하여 실패율을 구해준다.

// fail[i][0] = 스테이지 번호
// fail[i][1] = 실패율
const fail = Array.from(Array(N+1),(_,i)=>[i,0]); 
for(let i=1; i<=N; i++){
    fail[i][1] = unClear[i] / clear[i];
}

fail을 2차원 배열로 만든 이유는 정렬을 위해 스테이지의 번호와 실패율을 묶어서 저장하기 위함이다.

실패율을 모두 구했으면 정렬을 수행한다.

fail.sort((a,b)=>{
    if(b[1] === a[1]) return a[0] - b[0]; // 실패율이 같다면 스테이지 번호가 작은게 앞으로 가도록
    else return b[1] - a[1]; // 아니라면 실패율이 높은순으로 내림차순
}); 

그리고 정렬을 된 fail 배열을 이용해서 정답을 구한다.

for(const [stageNum, _] of fail){
    if(stageNum === 0) continue; // 0번 스테이지는 없으므로 스킵
    answer.push(stageNum);
}

코드

function solution(N, stages) {
    const answer = [];
    const clear = Array(N+2).fill(0); // 클리어한 플레이어의 수
    const unClear = Array(N+2).fill(0); // 클리어하지 못한 플레이어의 수
    // fail[i][0] = 스테이지 번호
    // fail[i][1] = 실패율
    const fail = Array.from(Array(N+1),(_,i)=>[i,0]); 
    
    for(let i=0; i<stages.length; i++){
        unClear[stages[i]]++; 
        for(let j=stages[i]-1; j>=1; j--){
            clear[j]++;
        }
    }
   
    for(let i=1; i<=N; i++){
        fail[i][1] = unClear[i] / clear[i];
    }
    
    fail.sort((a,b)=>{
        if(b[1] === a[1]) return a[0] - b[0]; // 실패율이 같다면 스테이지 번호가 작은게 앞으로 가도록
        else return b[1] - a[1]; // 아니라면 실패율이 높은순으로 내림차순
    }); 
    
    for(const [stageNum, _] of fail){
        if(stageNum === 0) continue; // 0번 스테이지는 없으므로 스킵
        answer.push(stageNum);
    }
    
    return answer;
}