문제 설명
실패율
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.
- 실패율은 다음과 같이 정의한다.
- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
제한사항- 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
- stages의 길이는 1 이상 200,000 이하이다.
- stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
- 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
- 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
5 | [2, 1, 2, 6, 2, 4, 3, 3] | [3,4,2,1,5] |
4 | [4,4,4,4,4] | [4,1,2,3] |
입출력 예 #1
1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.
- 1 번 스테이지 실패율 : 1/8
2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.
- 2 번 스테이지 실패율 : 3/7
마찬가지로 나머지 스테이지의 실패율은 다음과 같다.
- 3 번 스테이지 실패율 : 2/4
- 4번 스테이지 실패율 : 1/2
- 5번 스테이지 실패율 : 0/1
각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.
- [3,4,2,1,5]
입출력 예 #2
모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.
- [4,1,2,3]
풀이코드
import java.util.*;
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
int[] clearUser = new int[N+2]; // 클리어한 유저
double[] failRate = new double[N+2]; // 실패율
double[] failSort = new double[N+2]; // 실패율 정렬한 배열
int userCnt = stages.length; // 남은 유저수
// 클리어 유저 도출
for(int i=0; i<stages.length; i++) {
if(stages[i] <= N) {
clearUser[stages[i]]++;
}
}
// 실패율 도출
for(int i=1; i<clearUser.length; i++) {
failRate[i] = clearUser[i] / (double)userCnt;
failSort[i] = clearUser[i] / (double)userCnt;
userCnt -= clearUser[i];
if(userCnt == 0) { // userCnt가 0이 되면 ?/0 이 되기때문에 나눗셈 불가능하므로 1로바꿔주기
userCnt = 1;
}
}
// 실패율 정렬
Arrays.sort(failSort);
int answerIdx = 0;
// 내림차순 정렬을 못해서.. 뒤에서 부터 탐색한다.
for(int i=failSort.length-1; i>=0; i--) {
for(int j=1; j<failRate.length-1; j++) {
if(failRate[j] == failSort[i]) { // 같을때 j의 인덱스값을 넣어주면 스테이지 번호다.
answer[answerIdx] = j;
failRate[j] = -1; // 이미 들어간 실패율이 중복될수있으니 -1로 변환
answerIdx++;
continue;
}
}
}
return answer;
}
}
풀이 방법
각 스테이지의 실패율을 구하고 실패율이 높은 순서대로 스테이지를 배열에 담아서 리턴하는 문제이다.
스테이지별로 실패율을 어떻게 담을까 고민을 하다가 맵을쓰려했지만 중복값이 있을수있다고 생각하여 배열을 2개 생성하기로했다.
- 실패율과 정렬된 실패율 2개의 배열, 클리어한 유저를 담을 배열 총 3개의 배열을 선언한다.
- 클리어한 유저를 도출한다. 방식은 해당 배열의 인덱스를 스테이지로 가정하고 해당 스테이지를 클리어한 유저가있다면 증가연산을 사용하여 증가시켜준다.
- 실패율을 구해준다. 방식은 해당 스테이지를 클리어한 유저 / 현재남은 유저로 계산하고, 계산이 완료되면 유저수를 빼준다.
- 유저가0명일때 나눗셈이 성립할수 없기때문에 유저수를 1이라고 가정해주고 다음계산을 이어한다.
- 두개의 실패율 배열중 한개의 배열을 정렬한다( double형 배열을 내림차순을 못해서.. 오름차순으로 정렬했다.) 추후 공부해서 해결할 예정
- 오름차순을 했기때문에 정렬한 배열은 뒤에서 부터 탐색해준다.
- 정렬한 배열과 정렬되지않은 배열을 비교해서 순서대로 정답배열에 다시 담아준다. 방식은 정렬되지않은 배열의 인덱스는 스테이지 번호이기때문에 그 번호를 answer에 담아주면 되는것이다.
'알고리즘 > Programmers' 카테고리의 다른 글
[Programmers] 음양 더하기 (0) | 2021.11.20 |
---|---|
[Programmers] 로또의 최고 순위와 최저순위 (0) | 2021.11.20 |
[Programmers] 숫자 문자열과 영단어 (0) | 2021.11.16 |
[Programmers] 부족한 금액 계산하기 (0) | 2021.11.14 |
[Programmers] [1차] 비밀지도 (0) | 2021.11.10 |