프로그래머스 실패율 자바

문제

풀이

import java.util.*;

public class Pro_실패율 {
    public int[] solution(int N, int[] stages) {
        int[] answer = {};

        // 각 스테이지 유저 수 체크
        int[] arr = new int[N+2];
        for(int i = 0; i < stages.length; i++){
            arr[stages[i]]++;
        }

        // 구간합 배열
        int[] sum = new int[N+2];
        // 여기서는 N+1의 위치에 모든 스테이지를 클리어 한 사용자 수가 저장되어 있기 때문에
        // 구간합을 구하기 전에 구간합의 마지막 인덱스에 이 사용자를 미리 저장
        sum[N+1] = arr[N+1];
        // 구간합 구하기
        for(int i = N; i >= 1; i--){
            sum[i] = arr[i]+sum[i+1];
            // System.out.print(sum[i]+" ");
        }

        // 실패율 구하기
        Queue<Node> q = new PriorityQueue<>();
        for(int i = 1; i <= N; i++){
            double per = (double)arr[i] / sum[i];
            // 실수의 경우 0을 나누기 연산을 하면 NaN이 발생하므로
            // 실수 랩퍼 클래스의 isNaN을 이용해 NaN이라면 0 을 저장
            if(Double.isNaN(per)){
                per = 0;
            }
            // 큐에 스테이지와 성공률을 저장
            q.add(new Node(i,per));
        }

		// 실패율을 기준으로 정렬된 큐의 각 스테이지 정보를 배열에 저장
        int[] result = new int[N];
        for(int i = 0; i < N; i++){
            Node now = q.poll();
            result[i] = now.pos;
        }
        return result;
    }


}

class Node implements Comparable<programmers.Node>{
	// 스테이지 번호
    int pos;
    // 실패율
    double per;
    
    public Node(int pos, double per){
        this.pos = pos;
        this.per = per;
    }
    
    @Override
    public int compareTo(programmers.Node o){
        if(this.per == o.per){
            return this.pos - o.pos;
        }
        if(this.per > o.per){
            return -1;
        }else{
            return 1;
        }

    }
}

리뷰

구간합을 이용하면 좀 더 수월하게 풀 수 있는 문제였다.

1. 먼저 stages를 돌며 각 스테이지에 머물러 있는 유저 수를 배열 arr에 저장한다.

2. arr을 끝 인덱스부터 돌며 구간합을 구한다.

   • 이 때 n+2에는 모든 스테이지를 클리어한 유저 수를 기록하고 있으므로 구간합의 끝 인덱스에 이 값을 따로 저장해준다.
   • arr을 끝 인덱스부터 구하는 이유는 스테이지에 도달한 유저 수를 구해야 하기 때문인데,
     스테이지 n이상에 위치한 유저는 이미 n을 클리어하거나 n에 머물러 있는 상태이므로 끝 인덱스부터 구간합을 구해준다.

3. 구간합을 저장하고 있는 sum과 각 스테이지의 유저수를 저장한 arr을 활용해 실패율을 구한다.

   • 이 때 실수에서 0을 나누기 연산을 하면 NaN이 발생하게 되므로 이 경우 조건에서 제시한 것처럼 0을 저장한다.
   • 이렇게 구해진 실패율과 스테이지 정보를 우선순위 큐에 저장한다.

• 이 때 각 스테이지 정보를 나타내는 클래스 Node를 생성하는데 정렬이 필요하므로 Comparable<>을 상속한다.
  • 이때 조건에 따라 실패율을 기준으로 내림차순 정렬하고
    
  • 실패율이 같을 경우 스테이지 번호를 기준으로 오름차순 정렬을 한다.

4. 정답 배열 result를 생성해 우선순위 큐에서 값을 하나씩 빼 result에 저장한다.