[프로그래머스 JavaScript] 실패율

프로그래머스 Level1 실패율 -> 2019 KAKA BLIND 문제

 

문제 설명 : 이게 어떻게 Level 1의 문제인건지.... 가끔 프로그래머스 난이도가 의심이된다. (내 머리가 문제인가....)

여튼 각 스테이지별로 실패율을 계산하여 실패율에 따른 내림차순 정렬을 해주면된다.

 

저는 문제접근을 다음과 같이 구상했다.

1. 입력으로 주어지는 stages별 갯수 배열 -> 즉 실패율에 분자에 해당하는 값이다

스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 

2. 해당 스테이지에 도달한 플레이어 수 배열 -> 즉 실패율에 분모에 해당하는 값이다.

 스테이지에 도달한 플레이어 수

3. 위에서 계산한 값을 통해 실패율을 계산해준다.

4. 해당 조건을 정렬후 스테이지 번호 추출

function solution(N, stages) {
  var answer = [];
  //스테이지 오름차순 정렬
  stages.sort((a, b) => a - b);

  //스테이지 수(분자)
  let stageNum = new Array(N).fill(0);
  //(분모)
  let mod = new Array(N).fill(0);
  //실패율[스테이지번호][실패율]
  let fail = Array.from(Array(N), () => new Array(2).fill(0));

  //실패율 [스테이지 번호 초기화]
  for (let i = 0; i < N; i++) {
    fail[i][0] = i + 1;
  }

  //스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수
  for (let x of stages) {
    //최종 스테이지는 제외
    if (x > N) break;
    stageNum[x - 1] += 1;
  }

  let m = 0;
  //스테이지에 도달한 플레이어 수
  for (let i = 0; i < N; i++) {
    //stages길이 - 누적 stage길이 = 분모값
    mod[i] = stages.length - m;
    m += stageNum[i];
  }

  //실패율 계산
  for (let j = 0; j < N; j++) {
    fail[j][1] = stageNum[j] / mod[j];
  }

  //실패율에 따른 내림차순
  fail.sort((a, b) => {
    //실패율 동일시 작은 번호의 스테이지 기준 정렬
    if (a[1] === b[1]) {
      return a[0] - b[0];
    } else {
      return b[1] - a[1];
    }
  });

  //스테이지 번호만 추출
  for (let x of fail) {
    answer.push(x[0]);
  }

  return answer;
}

 

코드설명 : 위에 설명한 접근 방법대로 구현하여 풀었다.

실패율은 스테이지번호와 실패율 두개의 값을 위해 이차원 배열을 이용하였다. (sort함수 편하게 이용하기 위해)

 

플레이어 수 반복문에서는 제한사항에 있는 마지막 스테이지 클리어 사용자를 제외하기 위한 조건을 넣어준다.

마지막으로 실패율 계산시 실패율에 따른 내림차순을 기본적으로 하는데 실패율이 같을때 작은 스테이지 번호

기준으로 정렬 조건을 넣어준다.

 

시간복잡도는 sort()메소드에서 가장 크게 작용한다.

구글링 결과 일반적인 프로그래밍 언어의 내장 sort함수는 O(nlogN) 시간 복잡도를 가진다고 나와있다.

즉 위의 코드 시간복잡도는  O(nlogN) 이 된다.

 

* 위의 코드는 수정한 코드이다.

처음으로 풀었던 코드는 계속 중간중간 실패가 떠서 꾸역꾸역 수정을 해서 풀긴했지만 가독성이 심하게 떨어져서

다시 차근차근 생각해서 나름 가독성? 이해하기?쉽게 작성했다.

 

 

처음에 해결했던 코드

function solution(N, stages) {
  var answer = [];
  //스테이지 오름차순 정렬
  let newStages = stages.sort((a, b) => a - b);

  //실패율 담는 변수 [스테이지번호][실패율]
  let fail = Array.from(Array(N), () => Array(2).fill(0));

  //스테이지 번호 초기화
  for (let i = 0; i < N; i++) {
    fail[i][0] = i + 1;
  }

  //
  //stages[0]에 대한 분모, 스테이지 셋팅
  //
  //분모값
  let m = newStages.length;
  //중복 스테이지 판별
  let tmp = newStages[0];
  //중복 스테이지 개수
  let cnt = 1;

  //스테이지 길이만큼
  for (let i = 1; i < newStages.length; i++) {
    //현재 스테이지와 이전 스테이지가 다르다면
    if (tmp !== newStages[i]) {
      ////이전 스테이지 실패율 계산
      fail[tmp - 1][1] = cnt / m;

      //현재 스테이지로 정보 셋팅
      cnt = 1;
      m = newStages.length - i;
      tmp = newStages[i];
    }
    //중복된 스테이지
    else {
      cnt += 1;
    }

    //테스트케이스 2번처럼 계속 중복될 경우
    //마지막 i번째에서 cnt값이 1이 아닐경우 계산
    if (i === newStages.length - 1 && cnt !== 1) {
      fail[tmp - 1][1] = cnt / m;
    }
    //마지막 스테이지 클리어 사용자는 실패율에서 무시
    if (newStages[i] > N) break;
  }

  //스테이지별 실패율에 따른 오름차순
  fail.sort((a, b) => {
    //실패율이 같다면 작은 번호의 스테이지가 먼저 와야함!
    if (b[1] === a[1]) {
      return a[0] - b[0];
    } else {
      return b[1] - a[1];
    }
  });

  //스테이지 번호만 추출
  for (let x of fail) {
    answer.push(x[0]);
  }

  return answer;
}