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

풀이 과정

• 첫 번째 풀이 (너무 느림)
  1. 스테이지에 도달한 플레이어의 수 => 해당 스테이지보다 크거나 같은 스테이지에 있는 플레이어: filter()
  2. 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 => 해당 스테이지에 있는 플레이어: filter()
  3. 총 스테이지 수 N만큼 반복: for
  4. 각 스테이지에 대한 실패율을 계산해서 결과 배열에 담기: push() ([스테이지, 실패율])
  5. 실패율 기준으로 내림차순 정렬: sort()
  6. 스테이지 번호만 남기기: map()

• 두 번째 풀이
  1. 길이가 N인 결과 배열을 [스테이지, 0]로 초기화: map()
  2. stages 배열을 돌면서 해당하는 스테이지의 1번째 요소 증가(도달했으나 클리어하지 못한 플레이어 수 세기): forEach()
  이때 N보다 큰 스테이지는 모든 걸 클리어한 플레이어니까 셀 필요 없음
  3. result 배열을 돌면서 각 스테이지의 1번째 요소를 남은 플레이어 수로 나누어서 실패율로 바꾸기: map()
  이때 남은 플레이어의 수는 전체 플레이어 수에서 앞 스테이지에 머물러 있는 플레이어 수를 뺀 수
  5. 실패율 기준으로 내림차순 정렬: sort()
  6. 스테이지 번호만 남기기: map()

코드

• 첫 번째 풀이

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

• 두 번째 풀이

function solution(N, stages) {
  const result = Array(N)
    .fill([])
    .map((e, i) => [i + 1, 0]);
  let len = stages.length;
  stages.forEach((e) => {
    if (e <= N) {
      result[e - 1][1] += 1;
    }
  });
  result.map((e) => {
    const tmp = e[1];
    e[1] /= len;
    len -= tmp;
    return e;
  });
  return result.sort((a, b) => b[1] - a[1]).map((e) => e[0]);
}

🦾

처음에 풀고서 시간이 너무 오래 걸려서 힌트를 보고 다시 풀어봤다.
어떤 테스트 케이스는 거의 800배나 오래 걸림
2중 반복문의 시간 복잡도가 얼마나 큰지를 체감할 수 있었던 문제...