문제
- 문제 링크: 실패율
해설
- 자료구조:
- 시간복잡도:
(풀이과정)
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)
d
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)
'1-4. 코딩테스트 문제집(진행중) > PCCP(Lv1)' 카테고리의 다른 글
[PCCP] Lv1: 완주하지 못한 선수(42576) 해설 (0) | 2024.12.24 |
---|---|
[PCCP] Lv1: 카드 뭉치(159994) 해설 (0) | 2024.12.24 |
[PCCP] Lv1: 크레인 인형 뽑기 게임(64061) 해설 (0) | 2024.12.24 |
[PCCP] Lv1: 모의고사(42840) 해설 (0) | 2024.12.23 |
[PCCP] Lv1: 두 개 뽑아서 더하기(68644) (0) | 2024.12.17 |