Posted Dec 12, 2020 2020-12-12T22:50:00+09:00 by Daekyo Jeong
Updated Apr 13 2021-04-13T19:23:19+09:00
문제
실패율
접근
- 각 스테이지에 도전 중인 사람 수 세기
- 각 스테이지별 실패율 구하기
- 실패율로 정렬하여 정답 반환
1의 경우 해시 테이블을 이용하여 해결하였다.
2의 경우에 실패율은 (해당 스테이지에 도전중인 사람) / (전체 인원 - 해당 스테이지 이전에 도전중인 사람) 이다.
1스테이지부터 시작해서 실패율을 구해주며 전체 인원에서 해당 인원을 빼는 식으로 하면 O(N)에 해결가능하다.
마지막 3번의 경우는 실패율로 정렬을 하지만, 반환값은 스테이지이기 때문에, 실패율과 스테이지를 묶어서 정렬해야 한다.
나는 우선순위 큐를 이용하여 실패율을 구하여 우선순위 큐에 넣어주어 정렬을 따로 할 필요가 없도록 만들어주었다.
C++의 경우는 첫 번째 인자(실패율)은 내림차순, 두 번째 인자(스테이지)는 오름차순으로 정렬하기 위해 따로 정렬 기준을 작성해주었다.
파이썬의 경우는 heap자체가 최소힙, 즉 오름차순 정렬인데, 음수값을 활용하여 내림차순으로 사용해서 그런건지 두 번째 인자에 대한 추가적인 코드가 필요 없었다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| import heapq
def solution(N, stages):
failrate = []
answer = []
stage = [0] * (N+2)
for item in stages:
stage[item] += 1
person = len(stages)
for i in range(1,N+1):
if person:
heapq.heappush(failrate, (-(stage[i]/person),i))
person -= stage[i]
else:
heapq.heappush(failrate, (0,i))
while len(failrate):
rate, idx = heapq.heappop(failrate)
answer.append(idx)
return answer
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <vector>
#include <queue>
using namespace std;
int stage[505];
struct cmp{
bool operator()(pair<double, int> p1, pair<double, int> p2){
if(p1.first == p2.first){
return p1.second > p2.second;
}
else{
return p1.first < p2.first;
}
}
};
vector<int> solution(int N, vector<int> stages) {
vector<int> answer;
priority_queue<pair<double, int>, vector<pair<double, int>>, cmp> failrate;
for(int i = 0; i<stages.size(); i++){
stage[stages[i]]++;
}
int person = stages.size();
for(int i = 1; i<=N;i++){
if(person!= 0){
failrate.push({stage[i]/double(person), i});
person -= stage[i];
}
else{
failrate.push({0, i});
}
}
while(!failrate.empty()){
answer.push_back(failrate.top().second);
failrate.pop();
}
return answer;
}
|
