[문제풀이 후기] 프로그래머스 #42889 - 실패율

https://school.programmers.co.kr/learn/courses/30/lessons/42889

 

기본 상위 코드

const N = 5;
const stages = [2, 1, 2, 6, 2, 4, 3, 3];
const result = []; // 결과 배열

 

첫 번째 시도 (결과 : 성공)

 

접근 방식

1. stage 도달 인원, stage 미완료 인원 수 각각 계산
2. 실패율 계산 후, result 에 stage 번호와 함께 push
3. 실패율 및 stage 번호를 기준으로 정렬

for (let i = 1; i <= N; i++) {
  const overStage = stages.filter((stage) => stage >= i); // stage 도달 인원
  const currentStage = overStage.filter((stage) => stage === i); // stage 미완료 인원

  result.push({ stage: i, rate: currentStage.length / overStage.length });
}

result.sort((a, b) => b.rate - a.rate || a.stage - b.stage);

return result.map((item) => item.stage);

---

규칙

현재 stage 도달 인원 수 = (전체 인원 수 - 이전 stage 에 있는 사용자 수)
실패율 = (현재 stage 사용자 수 / 현재 stage 도달 인원 수)

초기 stage 도달 인원 수 = 전체 인원 수

 

두 번째 시도 (결과 : 성공)

 

접근 방식

1. 각 stage 별 사용자 수 배열을 생성하고 초기화
2. 현재 stage 도달 인원 수가 0 인 여부를 판단, 이후 실패율 계산
3. result 에 stage 번호와 함께 push
4. 다음 stage 인원 수 = 현재 stage 도달 인원 수 - 현재 stage 사용자 수
5. 실패율 및 stage 번호를 기준으로 정렬

 

// stage 0 (초기값), stage N+1 (stage N 을 통과한 사용자)
const currentStage = Array.from({ length: N + 2 }, () => 0);

stages.forEach((stage) => currentStage[stage]++);

// 현재 stage 도달 인원 수
let overStageCount = stages.length;

for (let i = 1; i <= N; i++) {
  const currentStageRate =
    overStageCount > 0 ? currentStage[i] / overStageCount : 0;

  result.push({ stage: i, rate: currentStageRate });

  overStageCount -= currentStage[i]; // 다음 stage 도달 인원 수 반영
}

result.sort((a, b) => b.rate - a.rate || a.stage - b.stage);

return result.map((item) => item.stage);

 

 

효과

메모리 : 72.4 KB -> 38.4 KB
시간 : 5224.99 ms -> 26.13 ms
시간 복잡도 : O (N * stages 길이) -> O (N + stages 길이)

 

후기

Amaze! Amaze! Amaze!