프로그래머스 - 실패율

이종호·2021년 4월 8일

알고리즘

목록 보기

4/10

내 풀이

function solution(N, stages) {
    var answer = [];
    let arr = [];
    for(let i = 0 ; i < N+2; i++){
      arr[i] = 0;
    }
  
    for(let i = 0 ; i < stages.length;i++){
      let val = stages[i];
      if(arr[val] == false){
        arr[val] = 1
      }else{
        arr[val] += 1
      }
    }
  // let len = arr.reduce((f, b) => f+b);
  let len = stages.length;
  answer[0] = -1
  for(let i = 1 ; i < arr.length-1; i++){
    if(len == 0){
      answer[i] = 0;
      continue;
    }
    answer[i] = arr[i]/len;
    len -= arr[i]
  }
  let notsortedArr = [...answer].slice(1);
  let sortedArr = answer.sort((a, b) => b-a).slice(0, arr.length-2);
  let newArr = [];
  for(let i = 0 ; i < sortedArr.length; i++){
    for(let j = 0; j < notsortedArr.length;j++){
      if(sortedArr[i] == notsortedArr[j] && !newArr.includes(j+1)){
        newArr[i] = j+1;
        break;
      }
    }
  }
    return newArr;
}

설명

일단 arr 배열을 N+2길이만큼 0으로 초기화한다.
stages를 돌면서
각 층에 몇명의 사람이 있는지 구한다. == arr

현재 존재하는 모든 사람의 수를 구한다.

각 층에 존재하는 사람들을 보면서 실패율을 구한다.

구한 실패율을 정렬한 배열과 그렇지 못한 배열로 복제한다.

두 배열을 차례로 조회하면서, 값에 해당하는 인덱스를 저장하고, 이미 들어가 있는 인덱스라면 다음 인덱스를 찾도록 했다.

아쉬웠던점

틀린 케이스 찾기

처음 풀이에서 통과하지 못했고, 질문하기에서 1, 6, 7, 9, 13, 23, 24, 25에 대한 틀린 케이스를 찾아 풀었다.
혼자 찾아봐야 함은 알지만.. ㅠㅠ
테스트 케이스도 어떤 부분에서 내가 놓치는지 정리해 놓으면 좋겠다는 생각이 든다.

우선 지금의 테케는. 0/0이 나오는 경우를 생각하지 못했다.

어떻게 이 생각을 이끌어 낼까

js의 여러 메소드 미숙

다른 사람 풀이를 보니 비슷한 접근을 했지만, 코드는 훨씬 간결했다.
깔끔해야 보기도 좋다
하루빨리 해당 메소드로 고치고 익숙해지려 노력하자.!!

잘 푼 사람들과의 비교

잘 보면 내 풀이와 패터쓴님 풀이는 안정적으로 100ms 안쪽으로 걸리는 반면
1등님의 풀이는 가끔 3000ms에서 6000ms이상 뛸때가 있다.

성능체크가 들어간다면, 이와 같은 식을 유지하긴 어려울 것 같다.

하지만 왜 이렇게 큰 성능 이슈를 발생시키는지 모르겠는데,

1등님 풀이

function solution(N, stages) {
    let ans = []

    for (let i = 1; i <= N; ++i) {
        let usersReachedCurrentStage   = stages.reduce((acc, curStage) => acc + ((curStage >= i) ? 1 : 0), 0)
        let usersStagnatedCurrentStage = stages.reduce((acc, curStage) => acc + ((curStage == i) ? 1 : 0), 0)
        if (usersReachedCurrentStage === 0) {
            ans.push({ 'stage': i, 'failRate': 0 })
            continue
        }

        ans.push({ 'stage': i, 'failRate': (usersStagnatedCurrentStage / usersReachedCurrentStage) })
    }

    return ans.sort((a, b) => {
        if (a.failRate > b.failRate) return -1
        if (a.failRate < b.failRate) return 1
        return a.stage - b.stage
    }).map(entry => entry.stage)
}

패터쓴님의 풀이를 살짝보고 따라해보기

function solution(N, stages) {
  let arr = [];

  for (let i = 0; i < N + 1; i++) {
    arr.push([0, 0, i + 1])
  }
  /*
  [
    [ 0, 0, 1 ],
    [ 0, 0, 2 ],
    [ 0, 0, 3 ],
    [ 0, 0, 4 ],
    [ 0, 0, 5 ],
    [ 0, 0, 6 ]
  ]
  */
  stages.forEach(el => arr[el - 1][0]++)
  /*
  [
    [ 1, 0, 1 ],
    [ 3, 0, 2 ],
    [ 2, 0, 3 ],
    [ 1, 0, 4 ],
    [ 0, 0, 5 ],
    [ 1, 0, 6 ]
  ]
  */
  let len = stages.length;
  for (let i = 0; i < arr.length; i++) {
    arr[i][1] = arr[i][0] / len;
    len -= arr[i][0]
  }
  /*
  [
    [ 1, 0.125, 1 ],
    [ 3, 0.42857142857142855, 2 ],
    [ 2, 0.5, 3 ],
    [ 1, 0.5, 4 ],
    [ 0, 0, 5 ],
    [ 1, 1, 6 ]
  ]
  */

  console.log(arr.slice(0, arr.length - 1).sort((a, b) => b[1] - a[1]).map(el => el[2]))
  // [ 3, 4, 2, 1, 5 ]
  
  // NaN이 나오는 예외가 있지만, sort함수에서 자동으로 0과 같이 젤 하단에 놓이게하기 때문에 별도의 처리를 하지 않아도 된다.
}