06. failure rate
Sunhyup Lee. (2024). To be a successful candidate for the coding test. goldenrabbit. p.125.
Problem solving
입력조건:
-
N: 스테이지의 수
-
stages: 각 사용자가 도전 중인 스테이지 번호가 담긴 배열
예를 들어, stages = [2, 1, 2, 6, 2, 4, 3, 3] 은 8명의 사용자가 각기 다른 스테이지에 도전 중이라는 의미
-
각 스테이지는 1번부터 N번까지 있고, N+1번 스테이지에 있는 사용자들은 모든 스테이지를 클리어 한 사용자이다.
실패율 정의:
-
실패율은 특정 스테이지에 도달했으나 클리어하지 못한 사용자 수를, 그 스테이지에 도달한 총 사용자 수로 나눈 값입니다.
-
실패율이 높은 스테이지부터 내림차순으로 스테이지 번호를 반환해야 합니다.
입출력 예시:
1) N = 5, stages = [2, 1, 2, 6, 2, 4, 3, 3] - 이 경우, 각 스테이지의 실패율을 계산한 수 결과는 [3, 4, 2, 1, 5] 이다.
- N = 4, stages = [4, 4, 4, 4, 4]
- 이 경우, 결과는 [4, 1, 2, 3]이다.
해결 과정 예시:
- 스테이지1: 8명 중 1명 실패 → 실패율 = 1/8
- 스테이지2: 7명 중 3명 실패 → 실패율 = 3/7
- 스테이지3: 4명 중 2명 실패 → 실패율 = 2/4
- 스테이지4: 2명 중 1명 실패 → 실패율 = 1/2
- 스테이지5: 0명 → 실패율 = 0/1
결과적으로 실패율이 높은 순서대로 스테이지를 정렬하면 [3, 4, 2, 1, 5]가 된다.
① The first way to solve the problem : 단계별 사용자 수 계산 후, 직접 실패율 계산
function solution(N, stages) {
// N: 스테이지의 수, stages: 각 사용자가 도전중인 스테이지 번호가 담긴 배열
let failureRates = [];
// filureRates: 각 스테이지의 번허와 실패율을 저장할 배열
let totalUsers = stages.length;
// totalUsers: 남은 사용자의 수, 초기값은 도전 중인 사용자들의 전체수(stage.length)
for (let stage = 1; stage <= N; stage++) {
let failedUsers = stages.filter(s => s === stage).length;
// 해당 스테이지에 도전 중인 사용자 수
let failureRate = totalUsers === 0 ? 0 : failedUsers / totalUsers;
// 스테이지에 도달한 사용자가 없을 경우 실패율 0
failureRates.push({ stage: stage, rate: failureRate });
// 실패율 배열에 (스테이지 번호, 실패율) 저장
totalUsers -= failedUsers;
// 다음 스테이지로 넘어가므로 도전한 사용자를 뺌
}
failureRates.sort((a, b) => {
// 실패율을 기준으로 내림차순 정렬, 실패율이 같으면 스테이지 번호 순으로 오름차순 정렬
if (b.rate === a.rate) {
return a.stage - b.stage; // 실패율이 같으면 스테이지 번호 기준 오름차순
}
return b.rate - a.rate; // 실패율 기준 내림차순
});
return failureRates.map(item => item.stage);
// 정렬된 스테이지 번호만 반환
}
// 예시 실행
let N = 5;
let stages = [2, 1, 2, 6, 2, 4, 3, 3];
console.log(solution(N, stages)); // 출력: [3, 4, 2, 1, 5]
🧐 시간복잡도는 어떨까?
[Done] exited with code=0 in 0.063 seconds
1. 사용자 수를 계산하는 단계: O(M)
// stage 배열을 한 번 순회하며, 각 사용자가 도전 중인 스테이지를 카운트한다.
stages.forEach(stage => {
stageCounts[stage]++;
});
2. 실패율을 계산하는 단계: O(N)
// 1번부터 N번까지의 각 스테이지에 대해 도전한 사용자 수와 실패율을 계산
for (let stage = 1; stage <= N; stage++) {
let failedUsers = stageCounts[stage];
let failureRate = 0;
if (totalUsers > 0) {
failureRate = failedUsers / totalUsers;
}
failureRates.push({ stage: stage, rate: failureRate });
totalUsers -= failedUsers;
}
3. 정렬 단계: O(N logN)
// 이 단계에서는 실패율을 기준으로 스테이지를 정렬
failureRates.sort((a, b) => {
if (b.rate === a.rate) {
return a.stage - b.stage;
}
return b.rate - a.rate;
});
4. 결과 배열 생성 단계: O(N)
// 정렬된 failureRates 배열에서 스테이지 번호만 추출
return failureRates.map(item => item.stage);
최종 시간 복잡도: O(N + N logN)
② The second way to solve the problem : 맵(Map)을 사용하여 실패율 계산
function solution(N, stages) {
let stageCounts = new Map();
stages.forEach(stage => {
if (stageCounts.has(stage)) {
stageCounts.set(stage, stageCounts.get(stage) + 1);
} else {
stageCounts.set(stage, 1);
}
});
let totalUsers = stages.length;
let failureRates = [];
for (let stage = 1; stage <= N; stage++) {
let failedUsers = stageCounts.get(stage) || 0;
let failureRate = 0;
if (totalUsers > 0) {
failureRate = failedUsers / totalUsers;
}
failureRates.push({ stage: stage, rate: failureRate });
totalUsers -= failedUsers;
}
failureRates.sort((a, b) => {
if (b.rate === a.rate) {
return a.stage - b.stage;
}
return b.rate - a.rate;
});
return failureRates.map(item => item.stage);
}
// 예시 실행
let N = 5;
let stages = [2, 1, 2, 6, 2, 4, 3, 3];
console.log(solution(N, stages)); // 출력: [3, 4, 2, 1, 5]
🧐 시간복잡도는 어떨까?
[Done] exited with code=0 in 0.064 seconds
1. 각 스테이지에 도달한 사용자 수 단계: O(M)
// stages 배열을 순회하며 각 사용자가 도전 중인 스테이지 번호를 Map객체에 저장
stages.forEach(stage => {
if (stageCounts.has(stage)) {
stageCounts.set(stage, stageCounts.get(stage) + 1);
} else {
stageCounts.set(stage, 1);
}
});
2. 실패율 계산 단계: O(N)
// 1번부터 N번까지의 각 스테이지에 대해 실패율을 계산하고, failureRates 배열에 저장
for (let stage = 1; stage <= N; stage++) {
let failedUsers = stageCounts.get(stage) || 0;
let failureRate = 0;
if (totalUsers > 0) {
failureRate = failedUsers / totalUsers;
}
failureRates.push({ stage: stage, rate: failureRate });
totalUsers -= failedUsers;
}
3. 실패율을 기준으로 정렬 단계: O(N logN)
// 실패율을 기준으로 failureRates 배열을 정렬
failureRates.sort((a, b) => {
if (b.rate === a.rate) {
return a.stage - b.stage;
}
return b.rate - a.rate;
});
4. 결과 배열 생성: O(N)
// 정렬된 failureRate 배열에서 스테이지 번호만 추출하여 새로운 배열 생성
return failureRates.map(item => item.stage);
최종 시간 복잡도: O(N + N logN)
③ The third way to solve the problem : 배열의 인덱스를 활용한 직접 계산
function solution(N, stages) {
let stageUsers = new Array(N + 1).fill(0);
// 각 스테이지에 도달한 사용자 수 카운트
stages.forEach(stage => {
if (stage <= N) {
stageUsers[stage]++;
}
});
let totalUsers = stages.length;
let failureRates = [];
for (let i = 1; i <= N; i++) {
if (totalUsers > 0) {
let failureRate = stageUsers[i] / totalUsers;
failureRates.push({ stage: i, rate: failureRate });
totalUsers -= stageUsers[i];
} else {
failureRates.push({ stage: i, rate: 0 });
}
}
failureRates.sort((a, b) => b.rate - a.rate || a.stage - b.stage);
return failureRates.map(x => x.stage);
}
// 예시 실행
let N = 5;
let stages = [2, 1, 2, 6, 2, 4, 3, 3];
console.log(solution(N, stages)); // 출력: [3, 4, 2, 1, 5]
🧐 시간복잡도는 어떨까?
[Done] exited with code=0 in 0.072 seconds
1. 각 스테이지에 도달한 사용자 수 단계: O(M)
// stages 배열을 순회하며 각 사용자가 도전 중인 스테이지 번호를 카운트하여 stageUsers 배열에 저장
stages.forEach(stage => {
if (stage <= N) {
stageUsers[stage]++;
}
});
2. 실패율 계산 단계: O(N)
// 1번부터 N번까지의 각 스테이지에 대해 실패율을 게산하고, failureRate 배열에 저장
for (let i = 1; i <= N; i++) {
if (totalUsers > 0) {
let failureRate = stageUsers[i] / totalUsers;
failureRates.push({ stage: i, rate: failureRate });
totalUsers -= stageUsers[i];
} else {
failureRates.push({ stage: i, rate: 0 });
}
}
3. 실패율을 기준으로 정렬 단계: O(N logN)
// 실패율을 기준으로 failureRates 배열에 정렬
failureRates.sort((a, b) => b.rate - a.rate || a.stage - b.stage);
4. 결과배열 정렬 단계: O(N logN)
// 정렬된 failureRates 배열에서 스테이지 번호만 추출하여 새로운 배열을 생성
return failureRates.map(x => x.stage);
최종 시간 복잡도: O(N + N logN)