[Javascript][Programmers] 실패율 - 2019 KAKAO

 

문제

• 키워드: 실패율, 내림차순(정렬)
• 고려사항: stages가 200,000이하 → O(NlogN) 이내의 시간 복잡도

 

나의 풀이

• 시간복잡도: O(M x N)

function solution(N, stages) {

    // ➊ 배열 초기화: O(N)
    const challengers = new Array(N).fill(0);
    const losers = new Array(N).fill(0);

    // ➋ 스테이지에 도달한 사용자 수와 도전하는 사용자 수 구하기: O(M x N)
    for (let stage of stages) {
        if (stage > N) {
            stage = N;
        } else {
            losers[stage - 1]++;
        }
        for (let i = 0; i < stage; i++) {
            challengers[i]++;
        }
    }

    // ➌ 실패율 계산: O(N)
    const failureRate = [];
    for (let i = 0; i < N; i++) {
        failureRate.push(losers[i] / challengers[i]);
    }

    // ➍ 내림차순 정렬: O(NlogN)
    const sorted = Array.from(failureRate.keys())
        .sort((a, b) => failureRate[b] - failureRate[a])
        .map(index => index + 1);

    return sorted;
}

stages 배열을 순회하며 각 플레이어의 현재 스테이지를 확인하고, 해당 정보를 바탕으로 challengers와 losers 배열을 업데이트합니다. 이후 각 스테이지의 실패율을 계산하여 failureRate 배열에 저장하고, 마지막으로 실패율을 기준으로 스테이지 번호를 내림차순 정렬하여 반환합니다.

 

문제점

• 스테이지에 도달한 사용자의 수를 구하는 과정에서 이중 반복문 사용
• 플레이어의 스테이지가 N보다 크면 N으로 조정
• 스테이지 번호를 반환하는 과정에서 발생하는 추가적인 연산: map(index => index + 1)

 

다른 풀이

• 시간복잡도: O(M + NlogN)

function solution(N, stages) {
  // ➊ 스테이지별 도전자 수를 구함
  const challenger = new Array(N + 2).fill(0);
  for (const stage of stages) {
    challenger[stage] += 1;
  }

  // ➋ 스테이지별 실패한 사용자 수 계산
  const fails = {};
  let total = stages.length;

  // ➌ 각 스테이지를 순회하며, 실패율 계산
  for (let i = 1; i <= N; i++) {
    if (challenger[i] === 0) {
      // ➍ 도전한 사람이 없는 경우, 실패율은 0
      fails[i] = 0;
      continue;
    }

    // ➎ 실패율 계산
    fails[i] = challenger[i] / total;

    // ➏ 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
    total -= challenger[i];
  }

  // ➐ 실패율이 높은 스테이지부터 내림차순으로 정렬
  const result = Object.entries(fails).sort((a, b) => b[1] - a[1]);

  // ➑ 스테이지 번호만 반환
  return result.map((v) => Number(v[0]));
}

• N번째 스테이지에 도달한 사용자 수 = (전체 사용자 수) - (N-1번째 스테이지에 도달한 사용자 수)
• stages의 데이터 값을 challenger의 인덱스로 사용 (값 자체를 인덱스로 활용)

 

---

Reference

코딩테스트 합격자 되기: 자바스크립트 편