알고리즘

프로그래머스 - 실패율

Heidong 2022. 8. 4. 21:03
반응형

 

 

 

내 풀이

import java.util.Arrays;

public class P_41 {
	
	public static int[] solution(int N, int[] stages) {
		
        int[] answer = new int[N];
        double[] rate = new double[N];
        
        // 스테이지 순차 증가
        int next_stage = 0;
        
        // 총 사용자 수
        int total_user = stages.length;
        
        Arrays.sort(stages); // 스테이지 정렬
        
        // 실패율 구하기
        for(int i=0; i<=N; i++) {
        	int cnt = 0;
        	next_stage++;
        	if(total_user < 0 || next_stage > N) {
        		break;
        	}
        	
        	for(int j=0; j<stages.length; j++) {
        		if(stages[j] == next_stage) {
        			cnt++;
        		}
        	}
        	rate[i] = (double)cnt / total_user; // 실패율
        	if(cnt != 0) {
        		total_user -= cnt;
        	}
        }
        
        for(int i=0; i<answer.length; i++) {
        	answer[i] = i+1;
        }
        
        // 실패율 내림차순 정렬
        // 삽입 정렬
        for(int i=1; i<N; i++) {
        	double target = rate[i];
        	int target2 = answer[i];
        	int j = i-1;
        	
        	// j가 0보다 크고, 현재 인덱스 i가 해당하는 실패율이 전 인덱스 위치보다 클때만 반복함.
        	// 전 인덱스보다 해당 인덱스가 클 동안
        	// 즉 순서 변경을 해야한다는 뜻.
        	// 큰 수를 앞으로 계속 이동
        	while(j >= 0 && target > rate[j]) {
        		rate[j+1] = rate[j];
        		answer[j+1] = answer[j];
        		j--;
        	}
        	// 반복문이 끝남 = 현재 인덱스가 전보다 더 작음
        	// 내림차순 정렬 됨
        	// j번째 원소 뒤에 현재 현재 인덱스인 더 작은 요소를 넣음.
        	rate[j+1] = target;
        	answer[j+1] = target2;
        }
        
        return answer;
    }

	public static void main(String[] args) {
		// 실패율
        
		int[] stages = {2, 1, 2, 6, 2, 4, 3, 3};
		int n = 5;
		
		int[] answer = solution(n, stages);
		
		for(int x : answer) {
			System.out.println(x);
		}
	}

}

 

주요 풀이 로직 순서

 

1. 실패율을 구함

2. 구한 실패율을 배열에 담아 삽입 정렬 실행하면서 answer 배열 같이 정렬

 

삽입 정렬에 관한 글

https://st-lab.tistory.com/179

 

자바 [JAVA] - 삽입 정렬 (Insertion Sort)

[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) - [현재 페이지] 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (He..

st-lab.tistory.com

 

 

다른 사람 풀이

class Solution {
    public int[] solution(int N, int[] stages) {
        int[] answer = new int[N];
        double[] tempArr = new double[N];
        int arrLength = stages.length;
        int idx = arrLength;
        double tempD = 0;
        int tempI = 0;
        for (int i = 0; i < arrLength; i++) {
            int stage = stages[i];
            if (stage != N + 1)
                answer[stage - 1] += 1;
        }
        for (int i = 0; i < N; i++) {
            int personNum = answer[i];
            tempArr[i] = (double) personNum / idx;
            idx -= personNum;
            answer[i] = i + 1;
        }

        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N - i; j++) {
                if (tempArr[j - 1] < tempArr[j]) {
                    tempD = tempArr[j - 1];
                    tempArr[j - 1] = tempArr[j];
                    tempArr[j] = tempD;

                    tempI = answer[j - 1];
                    answer[j - 1] = answer[j];
                    answer[j] = tempI;
                }
            }
        }
        return answer;
    }
}
반응형