[Java] 프로그래머스 : 실패율

https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

 

풀이

변수 설명

• N : 전체 스테이지의 개수 N
• stages : 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열
• answer : 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열
• noclear : 해당 스테이지를 클리어하지 못한 사용자 수를 담는 배열
• player : 스테이지에 도달한 플레이어 수/ 초기 사용자 수는 stages.length
• tmpf, tmpa : 정렬을 위한 임시 저장 변수

알고리즘은 다음과 같다

1. 해당 스테이지를 클리어하지 못한 사용자 수(noclear) 구하기

• for문으로 stages만큼 반복
  • 사용자가 멈춰있는 스테이지에 맞는 noclear 배열에 +1

2. 실패율을 구하기

• for문으로 스테이지 개수인 N 만큼 반복
  
  • 현재 스테이지와 실패율을 구해 fail배열에 저장
    • 실패율 : fail[i] = (double)noclear[i]/player
  • player에서 noclear[i]만큼 빼줌
  • answer에 스테이지(i) 저장

3. 구한 실패율과 스테이지를 내림차순으로 정렬

• 주의할 점은 실패율을 내림차순으로 정렬하지만, 실패율이 같을 경우 스테이지는 오름차순 정렬이라는 것이다.
  따라서 배열을 가장 큰수(맨 앞) 먼저 정렬하지 않고 가장 작은 수(맨 뒤) 부터 정렬한다.

풀이 코드

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N]; // 스테이지
        double[] fail = new double[N]; // 실패율
        int noclear[] = new int[N]; // 해당 스테이지(-1)를 클리어하지 못한 사용자 수

        for(int s : stages){
            if(s != N+1) noclear[s-1] += 1;
        }        
        
        // 실패율 구하기
        int player=stages.length;// 초기사용자 = stages.length
        for(int i=0; i<N; i++){
            fail[i]= (double)noclear[i]/player; // 실패율 저장
            player -= noclear[i];
            answer[i]=i+1;
        }
        
        double tmpf=0;
        int tmpa =0;
        // 실패율 정렬하면서 answer의 스테이지도 함께 순서바꿈
        for(int i = 0; i < N; i++){
            for (int j = 1; j < N - i; j++) {
                if(fail[j-1]<fail[j]){  // 가장 작은 수(맨뒤)부터 정렬
                    tmpf=fail[j-1];
                    fail[j-1]=fail[j];
                    fail[j]=tmpf;
                    
                    tmpa=answer[j-1];
                    answer[j-1]=answer[j];
                    answer[j]=tmpa;
                }
            }
        }

        return answer;
    }
}

 

---

다른사람풀이

hashmap을 사용해 스테이지와 실패율을 저장한 뒤 compare 함수로 정렬해주었다.

 

변수 설명

• N : 전체 스테이지의 개수 N
• stages : 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열
• answer : 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열
• noclear : 해당 스테이지를 클리어하지 못한 사용자 수
• player : 스테이지에 도달한 플레이어 수
• stagefail : 스테이지와 실패율을 저장할 hashmap (key : 스테이지, value : 실패율)
• list_entries : 스테이지를 오름차순, 실패율을 내림차순으로 정렬하기위한 Map.Entry 리스트
  
  

알고리즘은 다음과 같다.

1. 실패율을 구해 hasmap에 저장

• for문으로 스테이지 개수인 N 만큼 반복
  • 현재 스테이지와 stages배열을 비교해 같다면 noclear++
  • 현재 스테이지와 실패율을 구해 stagefail에 put
    • 실패율 = (스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수)
      = noclear / player
  • player에서 noclear만큼 빼주고, noclear 초기화

2. 구한 실패율을 내림차순으로 정렬

Collections.sort()

Java 에서의 정렬은 java.util.Collections클래스의 static 메소드인 sort()를 이용한다.

스테이지를 오름차순, 실패율을 내림차순으로 정렬하기 위한 Map.Entry 리스트를 정의한다. 

정렬해줄 객체가 사용자가 정의해준 객체이기 때문에 Collections.sort() 메소드의 매개변수로 정렬하고자 하는 List 변수명과, Comparator 인터페이스를 구현한 클래스의 인스턴스를 넘겨줄 것이다.

Comparator 

Comparator 은 두 매개변수 객체를 비교하는 역할로, 인터페이스 내에 선언된 compare() 메소드를 반드시 오버라이딩(구현)해줘야 한다. 인터페이스 형식이 interface Comparator<T>{...} 인데, T 는 객체 타입이 지정될 자리며, compare() 메소드 안에 객체를 비교할 기준을 정의해주면 된다. 객체를 비교하기 위해 compareTo() 함수를 사용한다.

스테이지를 오름차순, 실패율을 내림차순으로 정렬하는 코드는 다음과 같다.
collections와 comparator 을 import 해줘야한다.

// Map.Entry 리스트 작성
List<Map.Entry<Integer, Double>> list_entries = new ArrayList<Map.Entry<Integer, Double>>(stagefail.entrySet());

// key 오름차순, value로 내림차순정렬
// 비교함수 Comparator를 사용하여 오름차순으로 정렬
Collections.sort(list_entries, new Comparator<Map.Entry<Integer, Double>>() {
    // compare로 값을 비교
    public int compare(Map.Entry<Integer, Double> obj1, Map.Entry<Integer, Double> obj2) {
        // 내림 차순 정렬
        return obj2.getValue().compareTo(obj1.getValue());
    }
});

 

전체 풀이 코드

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        int noclear=0; // 해당 스테이지를 클리어하지 못한 사용자 수
        int player=stages.length;// 초기사용자 = stages.length
        Map<Integer, Double> stagefail = new HashMap<Integer, Double>(); // key:스테이지와 value:실패율

        // 실패율 구하기
        for(int i=1; i<=N;i++){
            for(int s : stages){
                if(s==i) noclear++;
            }
            if(player==0) stagefail.put(i,0.0);
            else{
                stagefail.put(i,(double)noclear/player); // 현재 스테이지와 실패율 put
                player -= noclear;
                noclear=0;
            }
        }

        // Map.Entry 리스트 작성
        List<Map.Entry<Integer, Double>> list_entries = new ArrayList<Map.Entry<Integer, Double>>(stagefail.entrySet());
        // key 오름차순, value로 내림차순정렬
        // 비교함수 Comparator를 사용하여 오름차순으로 정렬
        Collections.sort(list_entries, new Comparator<Map.Entry<Integer, Double>>() {
            // compare로 값을 비교
            public int compare(Map.Entry<Integer, Double> obj1, Map.Entry<Integer, Double> obj2) {
                // 내림 차순 정렬
                return obj2.getValue().compareTo(obj1.getValue()); // obj1이 obj2보다 크면 1, 같으면 0, 작으면 -1 반환
            }
        });

        int c=0;
        for(Map.Entry<Integer, Double> entry : list_entries) {
            answer[c]=entry.getKey(); c++; // 정렬한 list key값 answer에 넣기
        }
        return answer;
    }
}

 

 

 

+

참고

Java 정렬방법 Collections.sort()