0726
문제 설명
슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.
이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.
- 실패율은 다음과 같이 정의한다.
- 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.
제한사항
- 스테이지의 개수 N은
1이상500이하의 자연수이다. - stages의 길이는
1이상200,000이하이다. - stages에는
1이상N + 1이하의 자연수가 담겨있다.- 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
- 단,
N + 1은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
- 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
- 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은
0으로 정의한다.
입출력 예
N | stages | result |
|---|---|---|
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]
풀이 과정
이 문제는 각 스테이지별로 도전한 사람 중 실패한 사람의 비율을 구하여 스테이지를 제일 실패율이 높은 순서대로 정렬하는 문제입니다.
저는 아래의 알고리즘으로 이 문제를 해결하였습니다.
- 스테이지별 실패한 플레이어의 수와 도전한 플레이어의 수를 구합니다.
- HashMap을 활용하여 스테이지와 스테이지별 실패율을 저장합니다.
- HashMap에 들어있는 실패율 중 가장 큰 실패율부터 차근히 배열에 넣고 HashMap에서 제거하는 과정을 반복하며 실패율이 가장 높은 순서대로 스테이지 번호를 배열에 저장합니다.
그럼 코드와 함께 자세한 풀이를 보러 가봅시다!
public int[] solution(int N, int[] stages) {
int[] failPlayer = new int[N+2];// 실패한 플레이어 수
int[] totalPlayer = new int[N+2];// 해당 스테이지에 도전한 플레이어 수N은 스테이지의 개수를 의미합니다.
stages는 현재 플레이어가 멈춰있는 스테이지들입니다.
실패율을 구하기 위해서는 실패한 사람의 수/해당 스테이지에 도전한 사람의 수를 계산해야 하기 때문에 그 둘을 구하기 위한 배열인 failPlayer와 totalPlayer배열을 생성합니다.
이 때 길이가 N+2인 이유는 인덱스를 스테이지로 잡을 것이기 때문입니다.
1스테이지에 실패한 플레이어의 수는 failPlayer[1]에 저장하는 식이라고 생각하면 됩니다.
또한 문제 예시를 보면 모든 스테이지를 다 클리어한 사람의 현 스테이지는 N+1이 되기 때문에 overflow를 방지하기 위해 길이에서 1을 더 늘려주었습니다.
따라서 각 배열의 길이가 N+2가 된 것입니다.
for ( int stage : stages ) {
failPlayer[stage]++;
for ( int i = 1; i <= stage; i++) {
totalPlayer[i]++;
}
}이 부분은 실패한 플레이어의 수와 해당 스테이지에 도전하고 있는, 혹은 도전했던 플레이어의 수를 구하는 부분입니다.
failPlayer의 stage인덱스를 1씩 증가시킵니다.
이러한 작업을 통해 1인덱스에는 1스테이지에 머물고 있는 사람의 수가 저장되고, 2인덱스에는 2인덱스에 머물고 있는 사람의 수가 저장됩니다.
최종적으로는 각 스테이지별 머물고 있는 사람의 수를 담은 failPlayer배열이 완성이 되는 것이죠.
이 배열은 나중에 실패율을 구할지말지에 대한 여부를 판단할 때 쓰입니다.
그 다음으로는 해당 스테이지에 도전했던 사람의 수를 구합니다.
만약 현재 플레이어가 3스테이지에 있다면 1스테이지, 2스테이지, 3스테이지에 도전한 것이 됩니다.
따라서 for문을 통해 i가 1부터 stage까지 돌며 각 스테이지별로 도전한 사람의 수를 1씩 증가시킵니다.
이렇게 스테이지별로 도전한 사람의 수와, 머물고 있는 사람의 수를 구하게 되었습니다!
Map<Integer, Double> ratesMap = new HashMap<>();// 스테이지별 실패율
for ( int i = 1; i <= N; i++) {
// 1. 스테이지별 실패한 사람의 여부를 묻고 실패율 구하고 저장
double failRate = ( failPlayer[i] == 0 ? 0 : (double)failPlayer[i]/totalPlayer[i] );
ratesMap.put(i, failRate);
}이 부분은 스테이지별로 실패한 사람이 있는지에 대해 물은 뒤 실패한 사람이 한 명이라도 있다면 실패율을 구한 뒤 HashMap에 저장하는 부분입니다.
만약 4스테이지에서 실패한 사람이 없다면 실패율을 구하는 행동은 무의미하겠죠? 아무리 나눠도 0이니까요.
이 때, 자바에서는 정수/정수의 결과값이 항상 정수인 점을 주의해야합니다. 피연산자 둘 중 하나는 꼭 double로 형변환하여 나눠주세요.
이렇게 구해진 실패율은 key값과 함께 value값으로 HashMap에 저장됩니다.
이 문제에서
HashMap을 사용한 이유는 스테이지와 스테이지별 실패율이 긴밀한 연관관계를 가지고 있기 때문에key값과value값이 한 세트인HashMap자료구조를 사용하게 된 것입니다.
여기서 i는 스테이지를, failRate는 해당 스테이지의 실패율을 의미합니다.
이렇게 스테이지별 실패율까지 다 구하였습니다.
이제 정렬만 해주면 되겠네요. 고지가 눈 앞입니다.
int[] answer = new int[N];
for ( int i = 0; i < N; i++) {
int maxKey = 0;
double maxRate = -1;이 부분은 스테이지별 실패율을 비교하여 가장 실패율이 높은 스테이지부터 answer에 담기게 하는 부분입니다.
우선 내림차순 정렬될 스테이지를 저장할 answer배열을 N(스테이지 수)만큼 생성해줍니다.
실패율이 큰 스테이지 순으로 answer에 저장하기 위해 for문으로 answer.length(N)만큼 돌려줍니다.
maxKey변수는 가장 실패율이 높은 스테이지를 의미하며 스테이지는1부터 시작하므로0을 초깃값으로 주었습니다.maxRate변수는 가장 높은 실패율을 의미하며 실패율은0부터 시작하므로-1로 초기화를 해주었습니다.
for ( int key : ratesMap.keySet() ) {
double rate = ratesMap.get(key);
if ( rate > maxRate ) {
maxRate = rate;
maxKey = key;
}
}
answer[i] = maxKey;
ratesMap.remove(maxKey);
}
return answer;이제는 Map에 들어있던 값들을 하나하나 비교하며 answer에 넣어줄 차례입니다.
Map의 모든 Key를 모아서 Set 자료형으로 리턴하는 ratesMap.keySet()를 이용하여 ratesMap에 들어있는 key를 하나씩 가져옵니다.
이 때 주의할 점은 key를 가져온 것이므로 key를 활용하여 get()으로 value, 즉 실패율을 다시 가져와야 합니다.
실패율은 실수형이니까 당연히 double형으로 변수를 선언해야겠죠?
만약 실패율이 maxRate보다 크다면 maxRate를 해당 실패율로 바꾸고, 스테이지 또한 해당 실패율의 스테이지로 바꿔줍니다.
이렇게 기준값을 변경해주어 최종적으로 두 번째 for문이 끝났을 때 maxRate와 maxKey에는 각각 제일 높은 실패율과 해당 스테이지가 들어있게 됩니다.
이렇게 가져온 실패율 최대값은 answer배열에 넣어준 뒤,
rateMap에서 해당 실패율을 제거해줍니다.
Map자료구조는 가변적이기 때문에 값을 중간에 삭제해도 문제가 되지 않습니다.
이런식으로 최대값을 하나하나 찾아 answer에 넣어주면 내림차순정렬이 된 스테이지를 리턴할 수 있게 됩니다.
소스 코드
import java.util.*;
class Solution {
public int[] solution(int N, int[] stages) {
int[] failPlayer = new int[N+2];// 실패한 플레이어 수
int[] totalPlayer = new int[N+2];// 해당 스테이지에 도전한 플레이어 수
// 1. 실패한 플레이어 수와 도전한 플레이어 수 구하기
for ( int stage : stages ) {
failPlayer[stage]++;
for ( int i = 1; i <= stage; i++) {
totalPlayer[i]++;
}
}
Map<Integer, Double> ratesMap = new HashMap<>();// 스테이지별 실패율
for ( int i = 1; i <= N; i++) {
// 1. 스테이지별 실패한 사람의 여부를 묻고 실패율 구하고 저장
double failRate = ( failPlayer[i] == 0 ? 0 : (double)failPlayer[i]/totalPlayer[i] );
ratesMap.put(i, failRate);
}
int[] answer = new int[N];
for ( int i = 0; i < N; i++) {
int maxKey = 0;
double maxRate = -1;
for ( int key : ratesMap.keySet() ) {
double rate = ratesMap.get(key);
if ( rate > maxRate ) {
maxRate = rate;
maxKey = key;
}
}
answer[i] = maxKey;
ratesMap.remove(maxKey);
}
return answer;
}
}실행 결과
코드 참고 : 노 코딩 노 라이프
