[프로그래머스_Lv2] 실패율 ( by using JavaScript )

문제

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

코딩테스트 연습 - 실패율

 

How to Solve ?

 

[1] Hash

 

stages ( = [2, 1, 2, 6, 2, 4,  3, 3] )는 각 스테이지 별에 도착했지만, 실패한 사람들의 수를 의미한다.

 

그렇기에, 우선적으로 해야 하는 일이 있다면  " 스테이지 별로 실패한 인원"을 구해야 각 스테이지의 실패율을 확인할 수 있다는 생각을 하게 되었다.

 

그리하여 최근 자주 사용하고 있는 Hash를 사용했었는데, 문제의 일부를 간과하여, N 이상의 값이 존재할 수도 있고, N이내의 모든 값이 있지 않다는 사실을 알게 되었다.

 

그래서 Hash를 사용하지 않게 되었다.

 

 

[2] Array

 

N+1 만큼의 배열을 0으로 초기화해놓는다면, 위에서 겪었던 문제를 해결할 수 있었다.

 

이제 다음으로 해결해야 하는 문제는 " 2) 각 스테이지 별, 실패율을 계산하는 것 " 였는데! 이 문제는

 

각 스테이지별 실패 인원 / 총 스테이지 참가자 수 ( stages.length)를 나누고, 다음 스테이지로 넘어갈 때

 

총 스테이지 참가자 수 - 각 스테이지 실패 인원수를 빼주면 해결이 된다.

function solution(N, stages) {
  const answer = [];
  const map = new Array(N + 1).fill(0);
  let length = stages.length;

  stages.forEach((stage, index) => {
    map[stage] = (map[stage] || 0) + 1;
  });

  for (let i = 1; i <= N; i++) {
    answer.push([i, map[i] / length]);
    length -= map[i];
  }

  answer.sort((a, b) => b[1] - a[1]);

  return answer.map((each) => each[0]);
}

 

[3] 코드 정리

 

위의 코드가 지저분해서 아래의 코드로 수정을 했는데! 최악의 경우 1200ms가 넘는 경우가 존재하였다.

내가 생각 했을 때는 O(n)으로 보여서 문제가 없는 것 같은데, 아무래도 filter가 시간을 많이 잡아먹는게 아닐까? 생각한다. 이에 대한 궁금증은 공부해서 추가로 달아 놓도록 하겠다!

function solution(N, stages) {
  const answer = [];
  let length = stages.length;

  for (let i = 1; i <= N; i++) {
    let loser = stages.filter((stage) => stage === i).length;
    answer.push([i, loser / length]);
    length -= loser;
  }

  answer.sort((a, b) => b[1] - a[1]);

  return answer.map((each) => each[0]);
}