본문 바로가기
1-4. 코딩테스트 문제집(진행중)/PCCP(Lv1)

[PCCP] Lv1: 실패율(42889) 해설

by cogito21_cpp 2024. 12. 23.
반응형

문제

- 문제 링크: 실패율

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1) 

 

solution 2)

 

solution 3)

 

 

(C++)

solution 1)

- N: 스테이지 개수

- M: stages의 길이

- 각 스테이지의 인원을 기준으로 특정 스테이지에서 실패한 인원수와 각 스테이지에 도전한 적이 있는 인원수를 구하는 과정: O(N*M)

- 이후 실패율을 구할 떄 시간 복잡도: O(N)

- 이를 정렬할 때 시간 복잡도: O(NlogN)

- 최종 시간 복잡도: O(N*M + NlogN)

더보기
#include <vector>
#include <algorithm>

using namespace std;

// 문제에서 요구하는 조건대로 실패율을 정렬하는 함수
bool compare(pari<int, float>& a, pair<int, float>& b) {
    if (a.second == b.second)
        return a.first < b.first;
    return a.second > b.second;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer; // 최종 답
    vector<float> challenger(N + 2, 0.0); // 각 스테이지에 도달한 적이 있는 도전자 수
    vector<float> fail(N + 2, 0.0);   // 특정 스테이지에 실패한 도전자의 수
    
    // 각 스테이지의 인원을 기준으로 특정 스테이지에서 실패한 인원 수와 각 스테이지에 도전한 적이 있는 인원수를 구함
    for (int i = 0; i < stages.size(); ++i) {
        for (int j = 0; j <= stages[i]; j++)
            challenger[j]++;
        fail[stages[i]]++;
    }
    
    // failRatio는 실패율 저장, first는 stage 정보, second는 실패율
    vector<pair<int, float>> failRatio(N);
    
    // 스테이지 정보와 실패율 저장
    for (int i = 0; i < N; ++i) {
        failRatio[i].first = i + 1;
        
        if (challenger[i + 1] == 0)
            failRatio[i].second = 0;
        else
            failRatio[i].second = fail[i + 1] / challenger[i + 1];
    }
    
    // 계산한 실패율을 문제에서 제시한 조건에 맞게 정렬
    sort(failRatio.begin(), failRatio.end(), compare);
    
    // 최종 답을 반환하기 위해 실패율을 저장
    for (int i = 0; i < N; ++i) {
        answer.push_back(failRatio[i].first);
    }

    return answer;
}

solution 2) 누적합 활용

- 실패율 구하는 과정의 3개의 반복문은 모두 N번씩 반복하므로 시간 복잡도: O(N)

- 마지막 실패율을 정렬하는 시간 복잡도: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

더보기
#include <algorithm>
#include <vector>

using namespace std;

vector<int> solution(int N, vector<int> stages) {
    vector<int> remains(N+2, 0);     // 스테이지에 도달했으나 클리어하지 못한 플레이어
    vector<int> reached(N+3, 0);     // 스테이지에 도달한 플레이어 수
    vector<double> fail_ratio(N+1);  // 스테이지의 실패율
    vector<int> ret(N);
    
    // remains, reached로 fail_ratio 구하기
    for (int challenging_stage : stages) {
        ++remains[challenging_stage];
    }
    
    for (int i{N+1}; i > 0; --i) {
        reached[i] = reached[i+1] + remains[i];
    }
    
    for (int i{1}; i <= N; ++i) {
        fail_ratio[i] = ((reached[i] == 0) ? 0 : 1.o * remains[i] / reached[i]);
    }
    
    // fail_ratio를 기준으로 정렬
    for (int i{1}; i <= N; ++i) {
        ret[i-1] = i;
    }
    
    sort(ret.begin(), ret.end(), [&fail_ratio](int& lhs, int& rhs) {
        if (fail_ratio[lhs] == fail_ratio[rhs]) return lhs < rhs;
        return fail_ratio[lhs] > fail_ratio[rhs];
    });

    return ret;
}

solution 3)

더보기
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

bool cmp(pair<double,int> a, pair<double,int> b){
    if(a.first==b.first)return a.second<b.second;
    else return a.first>b.first;

}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double,int>> per;
    map<int, double> ma;
    int size = stages.size();

    for(int i=0;i <stages.size();i++){
        ma[stages[i]]++;
    }
    double minus_mem=0;
    for(int i=1; i<=N;i++){
        if(ma[i]==0){
            per.push_back({0,i});
            continue;
        }
        per.push_back({ma[i]/(size-minus_mem),i});
        minus_mem+=ma[i];
    }
    sort(per.begin(),per.end(),cmp);
    for(auto o: per){
       answer.push_back(o.second);
    }

    return answer;
}

solution 4)

더보기
#include <string>
#include <vector>

using namespace std;

 

(C#)

solution 1)

 

solution 2)

 

solution 3)

 

 

(Java)

solution 1)

- N: 스테이지의 개수

- M: stages의 길이

- challenger 배열 초기화하고 각 스테이지 도전자 수를 계산: O(N + M)

- 이 후 스테이지별로 실패율을 계산: O(N)

- 실패율을 기준으로 스테이지 정렬: O(NlogN)

- 총 시간 복잡도: O(2*N + M + NlogN)

- 최종 시간 복잡도: O(M + NlogN)

더보기
import java.util.HashMap;

class Solution {
    public int[] solution(int N, int[] stages) {
        // 스테이지별 도전자 수를 구함
        int[] challenger = new int[N + 2];
        for (int i = 0; i < stages.length; ++i) {
            challenger[stages[i]] += 1;
        }
        
        // 스테이지별 실패한 사용자 수 계산
        HashMap<Integer, Double> fails = new HashMap<>();
        double total = stages.length;
        
        // 각 스테이지를 순회하며, 실패율 계산
        for (int i = 1; i <= N; ++i) {
            if (challenger[i] == 0) { // 도전할 사람이 없는 경우, 실패율은 0
                fails.put(i, 0.);
            }
            else {
                fails.put(i, challenger[i] / total); // 실패율 구함
                total -= challenger[i]; // 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌
            }
        }
        // 실패율이 높은 스테이지부터 내림차순으로 정렬
        return fails.entrySet().stream().sorted((o1, o2) -> Double.compare(o2.getValue(), o1.getValue())).mapToInt(HashMap.Entry::getKey).toArray();
    }
}

solution 2)

solution 3)

 

 

(Python)

solution 1)

- N: 스테이지의 개수

- M: stages의 길이

- challenger 배열 초기화하고, 각 스테이지 도전자 수 를 계산할 때 시간복잡도: O(N + M)

- 스테이지별로 실패율을 계산하는데 필요힌 시간복잡도: O(N)

- 실패율을 기준으로 스테이지 정렬할 떄 시간복잡도: O(NlogN)

- 총 시간복잡도: O(2*N + M + NlogN)

- 최종 시간복잡도: O(M + NlogN)

더보기
def solution(N, stages):
    # 스테이지별 도전자 수를 구함
    challenger = [0] * (N + 2)
    for stage in stages:
        challenger[stage] += 1
    
    # 스테이지별 실패한 사용자 수 계산
    fails = {}
    total = len(stages)
    
    # 각 스테이지를 순회하며, 실패율 계산
    for i in range(1, N + 1):
        if challenger[i] == 0: # 도전한 사람이 없는 경우, 실패율은 0
            fails[i] = 0
        else:
            fails[i] = challenger[i] / total # 실패율 구함
            total -= challenger[i] # 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뺌

    # 실패율이 높은 스테이지부터 내림차순으로 정렬
    result = sorted(fails, key=lambda x : fails[x], reverse=True)
    
    return result

solution 2)

더보기
def solution(N, stages):
    answer = []
    stay = [0 for _ in range(N+2)]
    fail = dict()
    total = len(stages)
    
    for i in stages:
        stay[i] += 1
    
    for i in range(1, N+1):
        # 추가 안할경우 런타임 에러 발생(확인 필요)
        if stay[i] == 0:
            fail[i] = 0
        else:
            fail[i] = stay[i]/total
            total -= stay[i]
        
    answer = sorted(fail, key=lambda x:fail[x], reverse=True)
    return answer

# def solution(N, stages):
#     challenger = [0] *(N+2)
#     for stage in stages:
#         challenger[stage] += 1
        
#     fails = {}
#     total = len(stages)
    
#     for i in range(1, N+1):
#         if challenger[i] == 0:
#             fails[i] = 0
#         else:
#             fails[i] = challenger[i]/total
#             total -= challenger[i]
            
#     result = sorted(fails, key=lambda x: fails[x], reverse=True)
#     return result

solution 3)

 

 

(JavaScript)

solution 1)

- N: 스테이지의 개수

- M: stages의 길이

- challenger 배열 초기화하고, 각 스테이지 도전자 수 를 계산할 때 시간복잡도: O(N + M)

- 스테이지별로 실패율을 계산하는데 필요힌 시간복잡도: O(N)

- 실패율을 기준으로 스테이지 정렬할 떄 시간복잡도: O(NlogN)

- 총 시간복잡도: O(2*N + M + NlogN)

- 최종 시간복잡도: O(M + NlogN)

더보기
function solution(N, stages) {
    // 스테이지별 도전자 수를 구함
    const challenger = new Array(N + 2).fill(0);
    for (const stage of stages) {
        challenger[stage] += 1;
    }
    
    // 스테이지별 실패한 사용자 수 계산
    const fails = {};
    let total = stages.length;
    
    // 각 스테이지를 순회하며, 실패율 계산
    for (let i = 1; i <= N; ++i) {
        if (challenger[i] == 0) {
            // 도전한 사람이 없는 경우, 실패율은 0
            fails[i] = 0;
            continue;
        }
        
        // 실패율 계산
        fails[i] = challenger[i] / total;
        
        // 다음 스테이지 실패율을 구하기 위해 현재 스테이지의 인원을 뻄
        total -= challenger[i];
    }
        
    // 실패율이 높은 스테이지부터 내림차순으로 정렬
    const result = Object.entries(fails).sort((a, b) => b[1] - a[1]);
    
    // 스테이지 번호만 반환
    return result.map((v) => Number(v[0]));
}

 

solution 2)

 

solution 3)

 

 

반응형