실패율

#Algo #Array

📔 문제 설명

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

실패율은 다음과 같이 정의한다.
스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

📓 제약 조건

스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
stages의 길이는 1 이상 200,000 이하이다.
stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

📓 입출력의 예

N stages result
5 [2, 1, 2, 6, 2, 4, 3, 3] [3,4,2,1,5]
4 [4,4,4,4,4] [4,1,2,3]

❗ 1번째

첫번째로 필요한 함수에 대한 정리를 했습니다 단 한번에 정리를 할수있는 능력이 궁금해서 도중 테스트는 진행하지않고 시도를 해봤습니다.
첫번째로 필요한 로직은 스테이지별로 실패한 사람의 수를 구하는 함수입니다 이 로직의 리턴값은 각 스테이지별로 실패한 사람의 순서가 담긴 배열입니다.
두번째로 필요한 로직은 실패율을 구하는 함수입니다 이 로직의 리턴값은 오브젝트로 리턴되며 키값에는 스테이지 , 밸류값엔 실패율이 담겨있습니다
세번째로 필요한 로직은 오브젝트를 받고 밸류값으로 정렬하며 맞는 순서대로 값을 리턴하고 문자열이였던 배열값을 숫자로 바꿉니다

하지만 오류와 함께 실패했습니다.

✅ 실행 코드

function solution(N, stages) {
  const 실패한사람 = 실패수찾기(stages);
  const 실패율 = 실패율구하기(실패한사람);
  const 정답 = 배열(실패율);
  return 정답
}

// 스테이지별로 실패한사람 구하는 함수
function 실패수찾기(arr) {
  let result = [];
  for (const 실패자수 of arr) {
    result[실패자수 - 1]++;
  }
  return result;
}
// 실패율을 구하는 함수
function 실패율구하기(arr) {
  let obj = {};
  let num = arr.length
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == 0) {
      obj = {...obj, [`${i + 1}`] : 0} 
    }else{
        obj = {...obj, [`${i + 1}`] : arr[i] / num}
    }
    num -= arr[i]
  }
  return obj
}

// 객체를 정렬하고 결과값을 배열로 옮기는 함수
function 배열(obj) {
  const arr = Object.entries(obj)
    .sort(([, a], [, b]) => b - a)
    .map(([key]) => Number(key));
  return arr;
}

❗ 2번째

첫번째로 실패수찾기 함수에서는 result의 값을 초기화 하지않아 undefined에 값을 추가하는 상황이였습니다. 그렇기에 라운드의 값을 파라미터로 추가로 받아 배열을 초기화 시켜주었습니다

두번째로는 실패율을 구하는 함수에서 num값을 arr.length로 넣었습니다 당시엔 아무생각없이 넣었는데 생각해보니까 왜 넣은지 모르겠습니다. length로 넣었을땐 스테이지의 갯수를 구하니 값이 이상하게 나왔습니다 바꿔서 총 플레이의 수를 구하게 for문을 활용해서 값을 추가하였습니다.

다시 생각해보니 stages의 길이를 받을려했는데 실패한사람의 길이로 계산을 해서 이렇게 된거같습니다.

그리고 arr.length값에서 마지막 성공자는 빼야하니 -1을 해줬습니다.
덤으로 arr[i]의 값이 0일때 obj의 값이 0이 되야되는데 어짜피 생각해보니까 비어있는 값이면 0으로 할당되니 없어도되는 조건문이라 삭제했습니다

✅ 실행 코드

function solution(N, stages) {
  const 실패한사람 = 실패수찾기(N, stages);
  const 실패율 = 실패율구하기(실패한사람);
  const 정답 = 배열(실패율);
  return 정답;
}

// 스테이지별로 실패한사람 구하는 함수
function 실패수찾기(N, arr) {
  let result = new Array(N + 1).fill(0);
  for (const 실패자수 of arr) {
    result[실패자수 - 1]++;
  }
  return result;
}

// 실패율을 구하는 함수
function 실패율구하기(arr) {
  let obj = {};
  let num = 0;
  
  for (const cnt of arr) {
    num += cnt;
  }
  
  for (let i = 0; i < arr.length - 1; i++) {
    obj = { ...obj, [`${i + 1}`]: arr[i] / num };
    num -= arr[i];
  }
  return obj;
}

// 객체를 정렬하고 결과값을 배열로 옮기는 함수
function 배열(obj) {
  const arr = Object.entries(obj)
    .sort(([, a], [, b]) => b - a)
    .map(([key]) => Number(key));
  return arr;
}

❗ 3번째

추가적으로 되짚어보다가 찾은건데 entries는 문자열 배열로 리턴을해주니 Number값으로 바꿔주는 로직은 뺄수없었고 덤으로 이렇게 짠이유가 자바스크립트의 객체는 순서가 없는 객체지만 es6이후로 숫자는 오름차순으로 고정 문자열은 들어온 순서대로 고정이라 이렇게 짯던거였는데 생각해보니 entries를 거치고나면 어짜피 문자열이라 거추장하게 문자열로 밸류값을 넣지않아도 동작이 되지않을까해서 아래 처럼 바꿔보았습니다.

덤으로 스프레드 문법은 객체를 복사함으로 O(n2)에서 O(n)으로 최적화됩니다.

✅ 실행 코드

// 실패율을 구하는 함수
function 실패율구하기(arr) {
  let obj = {};
  let num = 0;
  
  for (const cnt of arr) {
    num += cnt;
  }
  
  for (let i = 0; i < arr.length - 1; i++) {
    obj[i + 1] = arr[i] / num;
    num -= arr[i];
  }
  return obj;
}

📚 문제 느낀점

뭔가 어려운 문제는 아니였지만 요구하는 부분이 되게 길어서 읽고 검증하는 과정이 중요할거같아서 도중에 테스트를 진행하지않고 전체 코드작성후 오류를 수정해보았습니다.

뭔가 놓친 부분이 너무 많고 작성을 하면서는 몰랐던 것들을 되짚어 보는 과정에서 조금 알고리즘을 푸는 시각이 넓어진거같습니다.

근데 왜 아직도 처음엔 들어오는 N값을 안쓴진 모르겠다 노력하겠습니다.

© 문제 출처

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