Algorithm/Problem_프로그래머스
프로그래머스(실패율) - Java
uyoo
2020. 5. 11. 21:26
[실패율]
https://programmers.co.kr/learn/courses/30/lessons/42889
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
* 로직
- 스테이지의 번호와 실패율을 담을 클래스를 생성한다
- stages 배열을 하나씩 탐색하며 카운팅 정렬(arr[])을 진행한다. 스테이지의 전체 개수(total)도 담아둔다
- 사전에 카운팅 정렬된 배열을 이용해 스테이지의 번호를 1부터 N까지 차례대로 탐색한다
- 스테이지에 도달한 유저가 없다면 -> 실패율은 0으로 정의한 후 우선순위 큐에 삽입
- 유저가 존재한다면
- arr[n]: n번째 스테이지에 도달했지만 클리어 못한 수
- total -= arr[1~n]: 스테이지에 도달한 플레이어 수
- 우선순위 큐에 담긴 정보 중, 가장 첫번째 루트 정보를 출력한다
import java.util.PriorityQueue;
class StageInfo implements Comparable<StageInfo>{
public double rate; //실패율
public int stageIdx; //스테이지 번호
public StageInfo(double rate, int stageIdx) {
this.rate = rate;
this.stageIdx = stageIdx;
}
@Override
public int compareTo(StageInfo o) {
if(this.rate < o.rate) return 1;
else if(this.rate == o.rate) return this.stageIdx - o.stageIdx;
return -1;
}
}
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = {};
int[] arr = new int[N+2]; //N+1이 들어오는 경우
int total = 0;
for(int stage : stages) {
arr[stage]++;
total++;
}
PriorityQueue<StageInfo> priorityQueue = new PriorityQueue<>();
for(int n=1; n<=N; ++n) {
double t = total;
// 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.
if(arr[n] == 0) {
priorityQueue.offer(new StageInfo(0, n));
}
else {
double notClearNum = arr[n]; // 해당 스테이지에 도달했지만 클리어를 못한 수
for(int i=1; i<n; ++i) {
t -= arr[i]; // 스테이지에 도달한 플레이어 수
}
priorityQueue.offer(new StageInfo(notClearNum/t, n));
}
}
answer = new int[priorityQueue.size()];
for(int i=0; i<answer.length; ++i) {
answer[i] = priorityQueue.poll().stageIdx;
}
return answer;
}
}