TIL: 실패율 (+ ChatGPT)

intro

[key, value]형태의 배열 또는 객체로 문제 푸는 방법에 대하여 배웠다.  (+ ChatGPT의 풀이 방법)

 

풀이

🔗 문제 링크

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

 

나의 풀이

처음에는 이전 시간에 배웠던 아래 코드를 활용하여 플레이어 수를 Object {key, value}형태를 반환해주었는데 그 상태에서 sort()인자를 배열 형태로 활용하려면 배열로 바꿔줘야하는 번거로움이 있었다. (+추가사항 ChatGPT의 풀이법을 통해 sort()인자를 배열형태로 받지 않아도 되는 걸 알게 되었다. [key. value]값을 돌려줄 때 꼭 이 형태 그대로 돌려야 하는 줄 잘못 알고 있었다. 아직 배열과 메서드에 익숙하지 않다는 걸 다시 한 번 느꼈다.)

map.set(a, (map.get(a) || 0) +1)

결론적으로 객체가 아닌 배열 형태로 push해주는 방법이 더 깔끔하였다. 게다가 플레이어수를 단순 Number로 반환해주니 식이 더 간단해질 수 있었다.

function solution(N, stages) {
    let lastPlayer = stages.length;
    let notClearPlayer;
    let fail = [];
    
    // 각 스테이지별 실패율을 구하고 배열 fail에 [스테이지 숫자, 실패율] 형태로 push
    // 1 스테이지부터 시작, N 스테이지까지
    for(i = 1; i <= N; i++){
        // 스테이지에 도달했으나 클리어하지 못한 플레이어 수
        notClearPlayer = stages.filter(v => v === i).length; // 1스테이지로 시작하니까 첫 값은 1이 됨 이걸 notClear에 할당
        // i = 1부터 n까지 숫자(스테이지) , 클리어 못한 플레이어 수 notClear을 남은 플레이어수로 나눔
        // 1 스테이지의 경우 모든 사람들이 도달했으므로 처음 할당받은 값인 전체 플레이어 수로 나눔
        fail.push([i, notClearPlayer / lastPlayer]);
        // 전체 플레이어수에서 1스테이지 플레이어수를 빼고 lastPlayer에 할당
        lastPlayer = lastPlayer - notClearPlayer
    }
    
    // fail 배열을 실패율(fail[1]) 순서로 정렬하여 스테이지 숫자(fail[0])만 리턴
    return fail.sort((a, b) => b[1] - a[1]).map(s => s[0]);
}

for문을 활용하여 스테이지를 순차적으로 돌려주면서 [스테이지, 실패율]을 구하였다.

 

 

다른 사람의 풀이

function solution(N, stages) {
    let result = [];
    for(let i=1; i<=N; i++){
        let reach = stages.filter((x) => x >= i).length;
        let curr = stages.filter((x) => x === i).length;
        result.push([i, curr/reach]);
    }
    result.sort((a,b) => b[1] - a[1]);
    return result.map((x) => x[0]);
}

reach에는 스테이지에 도달한(스테이지 넘버보다 크거나 같은) 플레이어 수,

curr에는 스테이지에 도달했으나 클리어하지 못한(스테이지 넘버와 같은) 플레이어 수를 구한 뒤

result에 [스테이지, 실패율(앞에서 구한 값을 나눔)]형태로 push한다.

뒷부분은 나의 풀이와 같다.

 

 

Chat GPT의 풀이

풀이 01

실패율을 계산하고 정렬하는 방식으로 문제를 해결합니다. 이 풀이의 시간 복잡도는 스테이지의 개수 N을 기준으로 O(N^2)입니다. 이는 각 스테이지에서 filter() 함수를 사용하여 해당 스테이지에 도달한 사용자 수를 계산하고, 마지막에 실패율을 기준으로 정렬하기 때문입니다

function solution(N, stages) {
  let userCount = stages.length; // 전체 사용자 수
  const failureRates = []; // 스테이지별 실패율을 저장할 배열

  // 스테이지 번호 1부터 N까지 반복하여 실패율 계산
  for (let stage = 1; stage <= N; stage++) {
    const userInStage = stages.filter((s) => s === stage).length; // 스테이지에 도달한 사용자 수
    const failureRate = userInStage / userCount; // 실패율 계산
    failureRates.push({ stage, failure: failureRate }); // 스테이지 번호와 실패율을 객체로 저장
    userCount -= parseInt(userInStage); // 현재 스테이지에 도달한 사용자 수를 전체 사용자 수에서 제외
  }

  // 실패율을 기준으로 내림차순으로 정렬
  failureRates.sort((a, b) => {
    if (a.failure === b.failure) {
      return a.stage - b.stage; // 실패율이 같은 경우 스테이지 번호로 오름차순 정렬
    }
    return b.failure - a.failure; // 실패율 기준 내림차순 정렬
  });

  // 정렬된 스테이지 번호를 배열로 추출하여 반환
  return failureRates.map((obj) => obj.stage);
}

실패율을 구하고 push하는 부분에서 나의 풀이와 차이가 있다.

여기서는 객체로 저장했지만, 나의 풀이에서는 배열로 저장한 것.

이 답변을 얻기 전에는 객체로 구하기 어렵거나 비효율적일 것으로 예상해서 배열로 바꾸게 되었는데, 그다지 영향이 없음을 알았다.

 

 

풀이 02

더 효율적인 방법입니다. 스테이지 번호별로 도달한 사용자 수를 한 번의 순회로 계산하고, 실패율을 계산하는 동시에 정렬을 수행합니다. 이를 위해 stages 배열을 한 번 순회하며 스테이지 번호별로 도달한 사용자 수를 카운팅하면서 실패율을 계산하고, 이를 객체 배열에 저장합니다. 그 후, 객체 배열을 실패율과 스테이지 번호를 기준으로 정렬합니다. 이 풀이의 시간 복잡도는 O(N)입니다.

function solution(N, stages) {
  const count = Array(N + 1).fill(0); // 스테이지 번호별 도달한 사용자 수를 저장할 배열

  // 스테이지 번호별 도달한 사용자 수 카운팅
  for (let stage of stages) {
    count[stage]++;
  }

  const failureRates = []; // 스테이지별 실패율을 저장할 배열
  let userCount = stages.length; // 전체 사용자 수

  // 실패율 계산 및 객체 배열에 저장
  for (let stage = 1; stage <= N; stage++) {
    const userInStage = count[stage]; // 스테이지에 도달한 사용자 수
    const failureRate = userInStage / userCount; // 실패율 계산
    failureRates.push({ stage, failureRate }); // 스테이지 번호와 실패율을 객체로 저장
    userCount -= userInStage; // 현재 스테이지에 도달한 사용자 수를 전체 사용자 수에서 제외
  }

  // 실패율을 기준으로 내림차순으로 정렬
  failureRates.sort((a, b) => b.failureRate - a.failureRate);

  // 정렬된 스테이지 번호를 배열로 추출하여 반환
  return failureRates.map((obj) => obj.stage);
}

이 풀이에서 처음 Array 생성시 길이를 N+1로 설정해주는 이유는 인덱스를 활용하기 위함이다. 스테이지는 0이 아닌 1부터 시작하므로 0번은 버리는 인덱스가 된다.

나의 풀이와의 차이점은 스테이지에 도달한 사용자 수를 구하는 코드와 실패율을 저장하는 코드가 하나로 묶여있냐, 분리되어있냐 하는 차이이다. ChatGPT는 기능을 분리하고 인덱싱을 이용해 스테이지에 도달한 사용자 수를 구했다는 점.

 

 

풀이 03

계수 정렬(Counting Sort)을 활용하여 효율적으로 문제를 해결해보겠습니다. 계수 정렬은 각 요소의 개수를 세어서 정렬하는 알고리즘으로, 요소의 범위가 제한되어 있을 때 효율적으로 동작합니다. 계수 정렬을 활용하여 각 스테이지별 도전자 수를 계산하는 부분에서 O(N)의 시간 복잡도를 가지게 됩니다. 따라서, 전체적인 시간 복잡도는 O(NlogN)입니다.

function solution(N, stages) {
  const userCount = stages.length; // 전체 사용자 수
  const stageCount = new Array(N + 1).fill(0); // 각 스테이지별 도전자 수를 저장할 배열
  const failureRates = []; // 스테이지별 실패율을 저장할 배열

  // 각 스테이지별 도전자 수 계산
  stages.forEach((stage) => {
    stageCount[stage]++;
  });

  // 실패율 계산 및 저장
  let remainingUsers = userCount; // 남은 사용자 수 초기화
  for (let stage = 1; stage <= N; stage++) {
    const userInStage = stageCount[stage]; // 스테이지에 도달한 사용자 수
    const failureRate = userInStage / remainingUsers; // 실패율 계산
    failureRates.push({ stage, failureRate }); // 스테이지 번호와 실패율을 객체로 저장
    remainingUsers -= userInStage; // 현재 스테이지에 도달한 사용자 수를 남은 사용자 수에서 제외
  }

  // 실패율을 기준으로 내림차순으로 정렬
  failureRates.sort((a, b) => {
    if (a.failureRate === b.failureRate) {
      return a.stage - b.stage; // 실패율이 같은 경우 스테이지 번호로 오름차순 정렬
    }
    return b.failureRate - a.failureRate; // 실패율 기준 내림차순 정렬
  });

  // 정렬된 스테이지 번호를 배열로 추출하여 반환
  return failureRates.map((obj) => obj.stage);
}

풀이 02와 거의 유사하지만 풀이 03에서는 실패율을 내림차순으로 정렬할 때 '실패율이 같을 경우' 조건이 추가되었음을 알 수 있다.

 

 

ChatGPT로 알아본 풀이 02와 03 비교

두 풀이를 비교했을 때, 대체적으로 유사한 방식으로 문제를 해결하고 있습니다. 하지만 몇 가지 작은 차이점이 있습니다.

 

1. 스테이지 도달한 사용자 수 카운팅 방식:

• 이전 코드: forEach 메서드를 사용하여 stages 배열을 순회하며 각 스테이지별 도달한 사용자 수를 카운팅합니다.
• 수정된 코드: for...of 문을 사용하여 stages 배열을 순회하며 각 스테이지별 도달한 사용자 수를 카운팅합니다.

2. 실패율 계산 및 객체 배열에 저장:

• 이전 코드: failureRates.push({ stage, failureRate })를 사용하여 스테이지 번호와 실패율을 객체로 저장합니다.
• 수정된 코드: failureRates.push({ stage: stage, failureRate: failureRate })를 사용하여 스테이지 번호와 실패율을 객체로 저장합니다.

두 코드 간의 성능 차이는 크지 않으며, 주요 차이점은 코드의 가독성과 스타일에 있을 수 있습니다. 수정된 코드에서는 좀 더 명시적으로 변수와 속성을 선언하는 방식을 사용하고 있습니다. 따라서, 가독성 면에서는 수정된 코드가 조금 더 명확하다고 할 수 있습니다. 성능 면에서는 큰 차이가 없으므로 선택은 개발자의 선호도에 따라 달라질 수 있습니다.