1. 게임 실패율

게임 안 한지도 꽤 된것 같네. 이번엔 실패율을 구하는 알고리즘을 짜는 문제이다. 각 스테이지당 통과한 사람 대비 플레이하고 있는 사람의 숫자를 보고 실패율을 계산해서 가장 실패율이 높은 스테이지부터 내림차순으로 실패율에 따른 스테이지를 정리한다음 리턴하면 된다. 예시를 통해 살펴보자

N           stages              result
5	[2, 1, 2, 6, 2, 4, 3, 3]   [3,4,2,1,5]
// 0번째 인덱스에 2라고 적혀있는것은 첫번째 사람이 아직 2스테이지를 수행중이라는 말
// 즉 2스테이지를 통과하지 못했다는 말. 
//그 말은, 총 3명이 2스테이지를 통과하지 못했다는 말이다.

입출력 예 #1
1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

3 번 스테이지 실패율 : 2/4
4 번 스테이지 실패율 : 1/2
5 번 스테이지 실패율 : 0/1
각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

[3,4,2,1,5]

** 단, 실패율이 같을경우 작은 번호의 스테이지가 먼저오도록 한다.

2. 접근방법

• psuedo code

• 우선 이 문제가 어떤 문제인지를 파악해야 한다.(완전탐색같은데?)

• 이중포문으로 돌려보면서 실패율을 계산하자

• { stage: i+1 , rate: stillPlayingNum / passedNum } 요런식으로 push해보자.

  • 그러고 나서 rate를 통해 sort하고 rate가 같으면 stage를 통해 sort하자

function solution(N, stages) {
  let answer = [];
  let result = [];
  let stillPlayingNum = 0;
  let passedNum = 0;

  for (let i = 0; i < N; i++) {
    let stage = i + 1;
    for (let j = 0; j < stages.length; j++) {
      if (stage <= stages[j]) passedNum++;
      if (stage === stages[j]) stillPlayingNum++;
    }
    answer.push({ stage: stage, rate: stillPlayingNum / passedNum });
    passedNum = 0;
    stillPlayingNum = 0;
  }

  answer = answer
    .sort((a, b) => {
      // rate는 내림차순으로
      if (a.rate > b.rate) return -1;
      // rate가 같을때 stage는 오름 차순으로
      if (a.stage > b.stage) return 1;
    })
    .map((result) => result.stage);

  return answer;
}

일단 다 풀긴 다 풀었다..놀라운건 베스트앨범처럼 obj를 사용했고 이중정렬을 했으며 api를 이어서 사용했다는 것이다!!

진짜 실력이 늘긴 느는구나 계속 풀고 배웠던걸 적용하고 복습하다보면 말이다.

근데 시간복잡도가 아쉽다. 이중포문때문이다.

이중포문을 쓰지 않는 방법을 알아보자. 이중포문을 쓰지 않고 푸는 방법은 사실상 없어보인다... 완전탐색이라서 그런가?