[Programmers 알고리즘][42889] 실패율

문제 설명

level 1
2019 KAKAO BLIND RECRUITMENT

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

• 실패율: 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

N	stages	result
5	[2, 1, 2, 6, 2, 4, 3, 3]	[3,4,2,1,5]
4	[4,4,4,4,4]	[4,1,2,3]

---

문제 풀이

1. 각 STEP에 도달한 수를 카운팅
2. 실패율(A/B)은 아래와 같은 규칙을 가진다.
3. 소요 시간: sort가 관건이라고 생각했기 때문에, zero(실패율 0인 케이스)는 따로 담아 concat으로 합쳤다.
   • 어차피 오름차순으로 STEP별 실패율을 검사하는 로직 (for문)이 있기 때문에, 차례대로 담아 정렬함

	STEP 1	STEP 2	STEP 3	STEP 4	STEP 5	STEP 6(Finish)
A (도달 O,Clear X)	1	3	2	1	0	1
B (도달 O)	8 (유저 수)	7 (8 - 1)	4 (7 - 3)	2 (4 - 2)	1 (2 - 1)	1 (1 - 0)

Check Point

어떻게 시간복잡도를 줄일 것인가? (js 사용시 어떻게 효율적으로 sorting 할 것인가..?)

• 실패율 기준으로 소팅 후 다시 STEP별 Array로 변환해야 해서 for문을 어떻게 하면 줄일 수 있을지 고민 많이 함 🥲
• map으로 value기준으로 sorting 후 getKeys()로 바로 배열로 변환하고 싶었지만 js로 구현 방법이 마땅치 않아 포기
  • stackOverflow에서 다 아래 코드 처럼 소팅하는 법만 알려줌...
  • 어차피 getKeys() 자체가 O(N)인가?
• 결국 sort하는 대상의 배열 수를 줄이는 방법을 택함...

Code

/**
 * level 1
 * 2019 KAKAO BLIND RECRUITMENT
 */
function solution(N, stages) {
    const People = stages.length;
    let step = new Array(N+2);
    stages.forEach(n => step[n] = (step[n] || 0)+1);

    let result = [];
    let num = People;
    let zero = [];
    for(let i=1; i<=N; i++) {
        if(!step[i]) {
            zero.push(i);
        } else {
            result.push([i, step[i]/num]);
            num -= step[i];
        }
    }

    result.sort((a, b) => {
        return b[1] - a[1];
    });
    return result.map(item => item[0]).concat(zero);
}

---

결과