[프로그래머스] 실패율

문제 요약

개발자 오렐리가 만든 오천성이라는 게임이 존재합니다. 이 게임의 실패율을 구하려고 합니다. 실패율을 구하는 공식은 아래와 같습니다.

• 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지 개수 N과 현재 머물러 있는 스테이지 번호가 담긴 stages 배열이 파라미터로 전달된됩니다. 이때 실패율이 높은 순으로 스테이지 정보를 배열로 반환하세요.

 

✅ 추가 정보

• 현재 스테이지에 머물러 있는 플레이어가 없는 경우 실패율은 0
• 실패율이 동일한 경우 스테이지가 낮은 순으로 반환
• 현재 머물러 있는 스테이지 값이 N + 1인 경우 모든 스테이지를 클리어한 경우

 

나의 생각

가장 단순하게 생각해보면 각 스테이지별로, stages에서 현재 머물러 있는 플레이어 정보와 클리어한 플레이어 정보를 추출하여 실패율을 구할 수 있습니다. 하지만 이 경우 500 * 200,000 번 반복문을 돌아야 하기 때문에 시간이 오래 걸릴거라 생각하였습니다.

이 문제를 해결하기 위해 현재 스테이지를 클리어한 플레이어와 머물러 있는 플레이어의 수를 누적하는 배열을 사용하였습니다. stages를 오름차순으로 정렬 후 위에서부터 클리어한 플레이어 정보 + 머물러 있는 플레이어 수를 저장합니다.

 

예를 들어 3스테이지에 머물러 있는 플레이어가 2명, 2스테이지에 머물러 있는 플레이어가 1명, 1스테이지에 머물러 있는 플레이어가 2명이라면 아래와 같이 표현될 수 있습니다.

 

1. 3스테이지에 머물러 있는 플레이어 정보

스테이지 1	스테이지 2	스테이지 3	전체 클리어
		2	0

 

2. 2스테이지에 머물러 있는 플레이어 정보

스테이지 1	스테이지 2	스테이지 3	전체 클리어
	3	2	0

 

3. 1스테이지에 머물러 있는 플레이어 정보

스테이지 1	스테이지 2	스테이지 3	전체 클리어
5	3	2	0

 

이를 통해서 stages를 반복문을 통해 확인 하지 않고 현재 스테이지를 클리어한 플레이어 수를 구할 수 있습니다. 

 

🤔 아래는 코드 작성 전 어떻게 코드를 작성할지에 대한 순서를 정리하였습니다.

 

1. 내림차순으로 정렬한다.

2. 모든 플레이어가 스테이지를 모두 클리어한 경우를 고려한다.

3. 가장 높은 스테이지 부터 반복문을 통해 실패율을 구한다.
4. stages 배열에 0번째 아이템을 확인한다.
4-1. 현재 스테이지보다 작은 값이면 실패율에 0, 인원수 정보에는 이전 인원수 정보를 저장한다.
4-2. 현재 스테이지랑 동일하면 배열에서 현재 스테이지랑 동일한 모든 값을 꺼낸다. 실패율을 계산하고 인원수도 저장한다.
5. 최종적으로 실패율을 정렬한다.

 

function solution(N, stages) {
    const fail = new Map();
    const stageInfo = [];
    stages.sort((a, b) => b - a);
    
    stageInfo[N + 1] = 0;
    const value = stages[0];
        
    if (value > N) {
        const index = stages.findIndex(s => N + 1 > s);
        
        if (index === -1) {
            return Array.from({ length: N }, (_, i) => i + 1);
        } else {
            stageInfo[N + 1] = index;
            stages.splice(0, index);
        }
    }
    
    for (let i = N; i > 0; i -= 1) {
        const value = stages[0];

        if (i > value || !value) {
            fail.set(i, 0);
            stageInfo[i] = stageInfo[i + 1];
        } else {
            const index = stages.findIndex(s => i > s);
            
            if (index === -1) {
                fail.set(i, stages.length / (stages.length + stageInfo[i + 1]));
                stages.splice(0, stages.length);    
            } else {
                fail.set(i, index / (index + stageInfo[i + 1]));
                stageInfo[i] = stageInfo[i + 1] + index;
                stages.splice(0, index);    
            }            
        }
    }
    
    return [...fail.entries()].sort((a, b) => {
        const diff = b[1] - a[1];
        
        if (diff === 0) {
            return a[0] - b[0]
        }
        
        return diff;
    }).map(([i]) => i);
}