- Published on
π οΈ[νλ‘κ·Έλλ¨Έμ€]-μ€ν¨μ¨
- Authors
- Name
- μ‘ μΉν
- @chihoon0415
πλ¬Έμ μ€λͺ
μνΌ κ²μ κ°λ°μ μ€λ 리λ ν° κ³ λ―Όμ λΉ μ‘λ€. κ·Έλ κ° λ§λ νλμ¦ μ€μ²μ±μ΄ λμ±κ³΅μ κ±°λμ§λ§, μμ¦ μ κ· μ¬μ©μμ μκ° κΈκ°ν κ²μ΄λ€. μμΈμ μ κ· μ¬μ©μμ κΈ°μ‘΄ μ¬μ©μ μ¬μ΄μ μ€ν μ΄μ§ μ°¨μ΄κ° λ무 ν° κ²μ΄ λ¬Έμ μλ€.
μ΄ λ¬Έμ λ₯Ό μ΄λ»κ² ν κΉ κ³ λ―Ό ν κ·Έλ λ λμ μΌλ‘ κ²μ μκ°μ λλ €μ λμ΄λλ₯Ό μ‘°μ νκΈ°λ‘ νλ€. μμ μνΌ κ°λ°μλΌ λλΆλΆμ λ‘μ§μ μ½κ² ꡬννμ§λ§, μ€ν¨μ¨μ ꡬνλ λΆλΆμμ μκΈ°μ λΉ μ§κ³ λ§μλ€. μ€λ 리λ₯Ό μν΄ μ€ν¨μ¨μ ꡬνλ μ½λλ₯Ό μμ±νλΌ.
μ€ν¨μ¨μ λ€μκ³Ό κ°μ΄ μ μνλ€.
= μ€ν μ΄μ§μ λλ¬νμΌλ μμ§ ν΄λ¦¬μ΄νμ§ λͺ»ν νλ μ΄μ΄μ μ
= μ€ν μ΄μ§μ λλ¬ν νλ μ΄μ΄ μ
μ 체 μ€ν μ΄μ§μ κ°μ N, κ²μμ μ΄μ©νλ μ¬μ©μκ° νμ¬ λ©μΆ°μλ μ€ν μ΄μ§μ λ²νΈκ° λ΄κΈ΄ λ°°μ΄ stagesκ° λ§€κ°λ³μλ‘ μ£Όμ΄μ§ λ, μ€ν¨μ¨μ΄ λμ μ€ν μ΄μ§λΆν° λ΄λ¦Όμ°¨μμΌλ‘ μ€ν μ΄μ§μ λ²νΈκ° λ΄κ²¨μλ λ°°μ΄μ return νλλ‘ solution ν¨μλ₯Ό μμ±νλΌ.
μ νμ¬ν
- μ€ν μ΄μ§μ κ°μ Nμ 1 μ΄μ 500 μ΄νμ μμ°μμ΄λ€.
- stagesμ κΈΈμ΄λ 1 μ΄μ 200,000 μ΄νμ΄λ€.
- stagesμλ 1 μ΄μ N + 1 μ΄νμ μμ°μκ° λ΄κ²¨μλ€.
- κ° μμ°μλ μ¬μ©μκ° νμ¬ λμ μ€μΈ μ€ν μ΄μ§μ λ²νΈλ₯Ό λνλΈλ€.
- λ¨, N + 1 μ λ§μ§λ§ μ€ν μ΄μ§(N λ²μ§Έ μ€ν μ΄μ§) κΉμ§ ν΄λ¦¬μ΄ ν μ¬μ©μλ₯Ό λνλΈλ€. λ§μ½ μ€ν¨μ¨μ΄ κ°μ μ€ν μ΄μ§κ° μλ€λ©΄ μμ λ²νΈμ μ€ν μ΄μ§κ° λ¨Όμ μ€λλ‘ νλ©΄ λλ€. μ€ν μ΄μ§μ λλ¬ν μ μ κ° μλ κ²½μ° ν΄λΉ μ€ν μ΄μ§μ μ€ν¨μ¨μ 0 μΌλ‘ μ μνλ€.
βοΈλ¬Έμ νμ΄
- C++ μ¬μ© ν¨μ
count()
ν¨μ- μ£Όμ΄μ§ λ²μ μμμ 맀κ°λ³μ κ°μ κ°―μλ₯Ό λ°ννλ ν¨μ
#include <algorithm> int ret = count(start_point, end_point, search_value);
stable_sort()
ν¨μ- μ£Όμ΄μ§ λ²μλ₯Ό stable_sort νλ ν¨μ.
stable_sort λ?
μ£Όμ΄μ§ μλ£κ΅¬μ‘°μ μλ μμλ μ μ§νλ©°, λΉκ΅ κ°λ§μ λμλ₯Ό λΉκ΅νμ¬ λμ΄νλ μ λ ¬
[[1,3],[1,27],[2,45],[2,6]]
λλ²μ§Έ μ리 stable_sort => [[1,3],[1,27],[2,6],[2,45]]#include <algorithm> stable_sort(start_point, end_point, operator(νμν κ²½μ° μμ±));
- Python μ¬μ© ν¨μ
divmod()
ν¨μsorted()
ν¨μ- 리μ€νΈμ λ΄μ₯ ν¨μ
sort()
μλ λ¬λ¦¬sorted()
ν¨μλ νμ΄μ¬ λ΄μ₯ ν¨μμ΄λ€. - μ λ ¬μ λ€μν μ€μ μ ν μ μλ€.
sorted(μ λ ¬_κ°μ²΄, ν€_맀κ°λ³μ, μ λ ¬μμ)
- 리μ€νΈμ λ΄μ₯ ν¨μ
β¨οΈνμ΄ μ½λ
- C++ μ½λ
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
vector<int> solution(int N, vector<int> stages) {
vector<int> answer;
vector<pair<int, float>> v;
sort(stages.begin(), stages.end());
int user = stages.size();
int finish_count = 0;
double temp;
for(int i = 0; i < N; i++) {
user -= finish_count;
if(user >= 1) {
finish_count = count(stages.begin(), stages.end(), i+1);
temp = finish_count / float(user);
v.push_back(make_pair(i+1, temp));
}
else {
v.push_back(make_pair(i+1, 0));
}
}
stable_sort(v.begin(), v.end(), [](const auto& a, const auto& b) {return a.second > b.second; });
for(auto it = 0; it < N; it++) {
answer.push_back(v[it].first);
}
return answer;
}
- νμ΄μ¬ μ½λ
def solution(N, stages):
answer = []
length = len(stages)
for i in range(N):
count = stages.count(i+1)
if count == 0:
fail = 0
else:
fail = count / length
answer.append((i+1, fail))
length -= count
answer = sorted(answer, key=lambda t: t[1], reverse=True)
answer = [i[0] for i in answer]
return answer