실패율

  1. 문제 정리
    • 실패율이 높은 스테이지를 내림차순으로
    • 만약 실패율이 같은 스테이지라면 작은 번호 스테이지가 먼저 오도록
    • 1스테이지: 멈춘 사람 1명 / 도달한 사람 8명 = 1/8 2스테이지: 멈춘 사람 3명 / 도달한 사람 7명 = 3/7 (1스테이지 통과한 7명) 3스테이지: 멈춘 사람 2명 / 도달한 사람 4명 = 2/4 (2스테이지 통과한 4명)
  2. 어려웠던 점
    • 스테이지별 멈춘 사람 수 = 현재 그 스테이지에서 게임을 멈춘 사람
    • 스테이지별 도달한 사람 수 = 그 스테이지까지 갈 수 있었던 사람 
        스테이지에 도달했으나 아직 클리어 하지 않은 플레이어의 수 / 스테이지 도달한 플레이어의 수
  3. 새롭게 알게 된 점
    • 문제 분석

      [!NOTE] N + 2 ? 💡 N 번째 스테이지를 클리어 한 사용자의 stage는 N+1 즉, 1스테이지를 클리어 했다면 2스테이지 일 것 배열의 인덱스는 0부터 시작이므로 N + 1 을 저장하려면 N +2 크기의 배열이 필요

1차 시도(약 20분)

N = 5 (총 5개 스테이지) 
┌─────────────────────────────────────┐ 
│ 1스테이지 → 2스테이지 → 3스테이지 → 4스테이지 → 5스테이지 │ └─────────────────────────────────────┘ 
										↓ 게임 완료!
stages = [2, 1, 2, 6, 2, 4, 3, 3]

stageCounts
1스테이지에서 멈춘 사람: 1명 (stages에서 '1' 개수) 
2스테이지에서 멈춘 사람: 3명 (stages에서 '2' 개수) 
3스테이지에서 멈춘 사람: 2명 (stages에서 '3' 개수) 
4스테이지에서 멈춘 사람: 1명 (stages에서 '4' 개수) 
5스테이지에서 멈춘 사람: 0명 (stages에서 '5' 개수)
→ 각 스테이지에서 실패해서 그만둔 사람

reachedPlayers
1스테이지에 도달한 사람: 8명 (모든 사람이 1스테이지는 시도) 
2스테이지에 도달한 사람: 7명 (1스테이지를 통과한 사람만) 
3스테이지에 도달한 사람: 4명 (2스테이지를 통과한 사람만) 
4스테이지에 도달한 사람: 2명 (3스테이지를 통과한 사람만) 
5스테이지에 도달한 사람: 1명 (4스테이지를 통과한 사람만)
→ 각 스테이지를 시도할 자격이 있는 사람

2차 시도(약 30분)


const stages = [2, 1, 2, 6, 2, 4, 3, 3];

// 스테이지별 멈춘 사람 수
let stageCounts = new Array(N + 2).fill(0); // N+1까지 가능하므로 
for (let stage of stages) { 
	stageCounts[stage] = stageCounts[stage] + 1;
	}

// 스테이지별 도달한 사람 수
let reachedPlayers = new Array(N + 2).fill(0);
let totalPlayers = stages.length;
for (let i = 1; i <= N; i++) {
	reachedPlayers[i] = totalPlayers;
	totalPlayers = totalPlayers - stageCounts[i];
}

// 실패율
let failureRates = [];
for (let i = 1; i <= N; i++){
	let rate = stageCounts[i] / reachedPlayers[i];
	failureRates.push({ stage: i, rate: rate });
}

//정렬
failureRates.sort((a, b) => b.rate - a.rate);

return failureRates.map(item => item.stage);

→ reachedPlayers[i] = 0 일 때가 고려되지 않았음. → 정렬에서 같은 실패율 일 때 정렬 기준이 고려되지 않았음.

3차 시도(약 20분)


function solution(N, stages) {
	// 스태이지
	let stageCounts = new Array(N + 2).fill(0); // N+1까지 가능하므로 
	for (let stage of stages) { 
		stageCounts[stage]++;
		}
	
	// 스테이지별 도달한 사람 수
	let reachedPlayers = new Array(N + 2).fill(0);
	let totalPlayers = stages.length;
	for (let i = 1; i <= N; i++) {
		reachedPlayers[i] = totalPlayers;
		totalPlayers -= stageCounts[i];
	}
	
	// 실패율
	let failureRates = [];
	for (let i = 1; i <= N; i++){
		let rate = reachedPlayers[i] === 0 ? 0 : stageCounts[i] / reachedPlayers[i];
		failureRates.push({ stage: i, rate: rate });
	}
	
	//정렬
	failureRates.sort((a,b) => {
		if (a.rate === b.rate) { 
			return a.stage - b.stage; 
		} 
		return b.rate - a.rate;
	});
	
	return failureRates.map(item => item.stage);
}

책 예제와 비교


function solution(N, stages) {
	// 중략
	
	const fails = {};
	let total = stages.length;

	for (let i = 1; i <= N; i++;) {
		if (challenger[i] === 0) {
			fails[i] = 0;
			continue;
		}

		fails[i] = challenger[i] / total;
		total -= challenger[i];
	}

	// 후략
}

This line appears after every note.

Notes mentioning this note

There are no notes linking to this note.

Here are all the notes in this garden, along with their links, visualized as a graph.