https://programmers.co.kr/learn/courses/30/lessons/42889
코딩테스트 연습 - 실패율
실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스
programmers.co.kr
내가 푼 방법
어떻게 풀었냐면...그냥 fail[] 배열을 만들어서 실패율을 넣고
배열의 뒤부터 큰걸 훑어서 제일 큰 수의 index를 answer[] 배열에 넣었다. 뒤부터 훑은 이유는 겹치는 수가 있으면 작은수부터 넣어야하니까..~~
그리고 index 넣은 수는 -2로 바꿔줬다.
진짜 몇시간동안 봤다. 어찌저찌 해서 냈더니 정답률 70이라 어이없어서ㅜㅠ 포기했다가 계속 붙잡고 풀었다.
혹시 안되는사람은
N = 4
stages = [1, 2, 3, 2, 1]
return = [3, 2, 1, 4]
테스트케이스 추가해서 해보길,,,
코드
class Solution {
public int[] solution(int N, int[] stages) {
int[] answer = new int[N];
double[] fail = new double[N+1];
for(int i : stages){ // fail[]에 스테이지에 있는 사람 수 넣음. 0부터 N까지 있음
if(i >= N+1)
fail[N]++;
else
fail[i-1]++;
}
for(int i = 0; i < N+1; i++){ // 실패율 구하기
int add = 0;
for(int j = i; j < N+1; j++){
add += fail[j];
}
if(fail[i] != 0)
fail[i] = fail[i] / add;
else {
fail[i] = 0; // 이거 꼭 해줘야한다...
}
}
for(int j = 0; j < N; j++){ // 뒤에서부터 훑어서 answer[] 배열에 넣기
int index = -1;
double big = -1;
for(int i = N-1; i > -1; i--){
if(fail[i] >= big) {
big = fail[i];
index = i;
}
}
if(index != -1){
fail[index] = -2;
answer[j] = index+1;
}
}
return answer;
}
}
휴 디게어렵네..킹받아.....
남의 코드 보기
import java.util.ArrayList;
import java.util.Collections;
class Solution {
static class Rate{
int idx; // stage number
double rate; // fail rate
public Rate(int idx, double rate) {
this.idx = idx;
this.rate = rate;
}
}
public static int[] solution(int N, int[] stages) {
int[] user_cnt = new int[N + 2]; // 각 stage에 머물러있는 user 수
int[] user_total_cnt = new int[N + 1]; // 각 stage에 도달한 전체 user 수
for (int i = 0; i < stages.length; i++) {
user_cnt[stages[i]]++;
}
// 스테이지에 도달한 유저 수 누적(?)하여 구하기
// 맨 마지막 stage는 n번째 + (n+1)번째
user_total_cnt[N] = user_cnt[N] + user_cnt[N + 1];
for (int i = N-1; i >= 1; i--) {
user_total_cnt[i] = user_cnt[i] + user_total_cnt[i + 1];
}
ArrayList<Rate> arr = new ArrayList<>(); // stage 번호와 실패율을 저장
for (int i = 1; i <= N; i++) {
if(user_total_cnt[i]==0){ //스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0
arr.add(new Rate(i, 0));
continue;
}
double rate = (double) user_cnt[i] / user_total_cnt[i];
arr.add(new Rate(i, rate));
}
// fail rate가 높은 순으로 sorting
Collections.sort(arr, ((o1, o2) -> Double.compare(o2.rate, o1.rate)));
// sorting 된 실패율의 stage 번호 저장
int[] answer = new int[N];
for (int i=0; i<arr.size(); i++) {
answer[i] = arr.get(i).idx;
}
return answer;
}
}
어렵다!
Rate 클래스를 따로 만들어서 비율을 계산하는 메서드를 만들었다.
저렇게 하면 arraylist에 map 형식으로 (index, rate) 로 저장할 수 있나보다. ㄷㄷ
Collections.sort를 이용해 실패율이 높은 순서대로 sorting 해줬다.
Arrays.sort(jobs, (o1, o2) -> o1[1].compareTo(o2[1])); // String 배열 오름차순
이런식으로 쓰나보다;;;;;;
다른 블로그도 쭉 훑어보니 stage 번호와 실패율을 따로 저장해서 맞춰놓고 stage 번호를 answer에 저장하는 식으로 진행했다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public int[] solution(int N, int[] lastStages) {
int nPlayers = lastStages.length;
int[] nStagePlayers = new int[N + 2];
for (int stage : lastStages) {
nStagePlayers[stage] += 1;
}
int remainingPlayers = nPlayers;
List<Stage> stages = new ArrayList<>();
for (int id = 1 ; id <= N; id++) {
double failure = (double) nStagePlayers[id] / remainingPlayers;
remainingPlayers -= nStagePlayers[id];
Stage s = new Stage(id, failure);
stages.add(s);
}
Collections.sort(stages, Collections.reverseOrder());
int[] answer = new int[N];
for (int i = 0; i < N; i++) {
answer[i] = stages.get(i).id;
}
return answer;
}
class Stage implements Comparable<Stage> {
public int id;
public double failure;
public Stage(int id_, double failure_) {
id = id_;
failure = failure_;
}
@Override
public int compareTo(Stage o) {
if (failure < o.failure ) {
return -1;
}
if (failure > o.failure ) {
return 1;
}
return 0;
}
}
}
스테이지의 플레이어의 수는 배열처럼 0이 아니라 1부터 시작할거라 N의 크기 +2를 하고 시작한다.
스테이지마다 플레이어 수 더해주고
id(stage 번호)와 failure을 짝지을 Stage 클래스를 따로 만들었다. 실패율 비교하는 메소드를 만들어서 비교.....
Comparable<T> 인터페이스
Comparable 인터페이스는 객체를 정렬하는 데 사용되는 메소드인 compareTo() 메소드를 정의한다.
자바에서 같은 타입의 인스턴스를 서로 비교해야하는 클래스들은 모두 Comparable 인터페이스를 구현함..
Boolean을 제외한 래퍼 클래스나 String, Time, Date와 같은 클래스의 인스턴스는 모두 정렬 가능하닷
기본 정렬 순서는 오름차순이다.
예제
class Car implements Comparable<Car> {
private String modelName;
private int modelYear;
private String color;
Car(String mn, int my, String c) {
this.modelName = mn;
this.modelYear = my;
this.color = c;
}
public String getModel() {
return this.modelYear + "식 " + this.modelName + " " + this.color;
}
public int compareTo(Car obj) {
if (this.modelYear == obj.modelYear) {
return 0;
} else if(this.modelYear < obj.modelYear) {
return -1;
} else {
return 1;
}
}
}
public class Comparable01 {
public static void main(String[] args) {
Car car01 = new Car("아반떼", 2016, "노란색");
Car car02 = new Car("소나타", 2010, "흰색");
System.out.println(car01.compareTo(car02));
}
}
실행결과 : 1
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스] 조이스틱 for JAVA _ 그리디 알고리즘 (0) | 2022.01.03 |
|---|---|
| [프로그래머스] 약수의 개수와 덧셈 for JAVA (0) | 2021.12.18 |
| [프로그래머스] 폰켓몬 for JAVA (0) | 2021.12.13 |
| [프로그래머스] K번째수 for JAVA (0) | 2021.12.08 |
| [프로그래머스] 소수 만들기 for JAVA (0) | 2021.11.26 |