[프로그래머스] 실패율

2019 카카오 채용 코딩 테스트 문제입니다.

코딩테스트 연습 - 실패율

문제 확인

 

prefix sum 활용 문제입니다.

 

풀이

 

입력받은 스테이지를 읽으면서 해당 스테이지에 몇 명이 있는지 기록합니다.

그 후 역순으로 읽어가면서 실패율을 구합니다.

실패율 = ary[i] / SUM( ary[i], ary[i+1], ... ary[N])

 

실패율을 전부 구하고 나면 실패율 순서대로 정렬하고 인덱스를 따로 추출하여 출력합니다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct pir {
    int idx;
    double fail;
};
vector<int> solution(int N, vector<int> stages) {
    vector<int> answer(N);
    pir ary[502] = { 0 };
 
    for (auto t : stages)
        ++ary[t - 1].fail;//인원수 기록
 
    double t = ary[N].fail;//prefix sum
    for (int i = N - 1; i >= 0; i--) {
        ary[i].idx = i;//인덱스 기록
        
        t += ary[i].fail;
        ary[i].fail = t ? ary[i].fail / t : 0;//실패율 기록
    }
    sort(ary, ary + N, [](const pir& a, const pir& b)->bool {//정렬
        if(a.fail!=b.fail)
            return a.fail > b.fail;
        return a.idx < b.idx;
    });
 
    for (int i = 0; i < N; i++) {//인덱스 추출
        answer[i] = ary[i].idx + 1;
    }
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.02ms, 3.97MB)
테스트 2 〉	통과 (0.02ms, 3.96MB)
테스트 3 〉	통과 (0.15ms, 4.02MB)
테스트 4 〉	통과 (0.36ms, 6.52MB)
테스트 5 〉	통과 (0.69ms, 9.84MB)
테스트 6 〉	통과 (0.04ms, 3.94MB)
테스트 7 〉	통과 (0.06ms, 3.89MB)
테스트 8 〉	통과 (0.38ms, 6.59MB)
테스트 9 〉	통과 (0.69ms, 9.95MB)
테스트 10 〉	통과 (0.31ms, 6.34MB)
테스트 11 〉	통과 (0.36ms, 6.59MB)
테스트 12 〉	통과 (0.49ms, 7.87MB)
테스트 13 〉	통과 (0.55ms, 8.31MB)
테스트 14 〉	통과 (0.02ms, 3.96MB)
테스트 15 〉	통과 (0.29ms, 5.25MB)
테스트 16 〉	통과 (0.15ms, 4.43MB)
테스트 17 〉	통과 (0.28ms, 5.33MB)
테스트 18 〉	통과 (0.16ms, 4.31MB)
테스트 19 〉	통과 (0.04ms, 3.95MB)
테스트 20 〉	통과 (0.18ms, 4.72MB)
테스트 21 〉	통과 (0.35ms, 6.16MB)
테스트 22 〉	통과 (1.00ms, 9.95MB)
테스트 23 〉	통과 (0.70ms, 9.64MB)
테스트 24 〉	통과 (0.59ms, 9.62MB)
테스트 25 〉	통과 (0.01ms, 3.95MB)
테스트 26 〉	통과 (0.01ms, 3.97MB)
테스트 27 〉	통과 (0.01ms, 3.91MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0