포브스 잡지는 매년 전 세계 최고 부자들의 순위를 발표합니다. 이 문제에서는 특정 연령대 내에서 가장 부유한 사람들을 찾는 시뮬레이션을 구현해야 합니다. N명의 자산 정보가 주어지면, 각 질의에 대해 지정된 연령 범위 [Amin, Amax] 내에서 자산이 가장 많은 M명을 출력하는 것이 목표입니다.
입력 형식
첫 줄에 사람 수 N과 질의 수 K가 주어집니다. 다음 N줄에는 각각 이름(8자 이하, 공백 없음), 나이(0~200), 자산(정수)이 주어집니다. 마지막 K줄에는 각 질의에 대해 출력할 최대 인원 M, 최소 나이 Amin, 최대 나이 Amax가 주어집니다.
출력 형식
각 질의마다 Case #X:를 먼저 출력하고, 조건을 만족하는 사람들을 다음 순서로 정렬하여 출력합니다:
- 자산 내림차순
- 자산이 같으면 나이 오름차순
- 둘 다 같으면 이름 사전순
해당 인원이 없으면 None을 출력합니다.
최적화 전략
단순히 전체를 정렬 후 매 질의마다 선형 탐색하면 시간 초과가 발생할 수 있습니다. 다음과 같은 접근이 필요합니다:
방법 1: 연령별 인덱싱
각 연령(0~200)에 대해 미리 정렬된 리스트를 만들어두고, 질의 시 해당 범위의 연령들에서 상위 M명을 추출하는 방식입니다.
#include <bits/stdc++.h>
using namespace std;
struct Individual {
string identity;
int years;
int fortune;
};
bool rankingRule(const Individual& x, const Individual& y) {
if (x.fortune != y.fortune) return x.fortune > y.fortune;
if (x.years != y.years) return x.years < y.years;
return x.identity < y.identity;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int totalPeople, queries;
cin >> totalPeople >> queries;
vector<Individual> database(totalPeople);
for (int i = 0; i < totalPeople; i++) {
cin >> database[i].identity >> database[i].years >> database[i].fortune;
}
sort(database.begin(), database.end(), rankingRule);
// 연령별로 미리 필터링된 벡터 구성 (최대 201개 연령)
vector<vector<Individual>> ageBuckets(201);
for (const auto& person : database) {
ageBuckets[person.years].push_back(person);
}
for (int q = 1; q <= queries; q++) {
int limit, minAge, maxAge;
cin >> limit >> minAge >> maxAge;
cout << "Case #" << q << ":\n";
vector<Individual> candidates;
// 해당 연령 범위의 모든 사람 수집
for (int age = minAge; age <= maxAge && candidates.size() < limit * 201; age++) {
for (const auto& p : ageBuckets[age]) {
candidates.push_back(p);
if (candidates.size() > limit * 100) break; // 과도한 메모리 방지
}
}
// 이미 전체 정렬되어 있으므로 상위 limit개 출력
if (candidates.empty()) {
cout << "None\n";
} else {
int outputCount = min(limit, (int)candidates.size());
for (int i = 0; i < outputCount; i++) {
cout << candidates[i].identity << " "
<< candidates[i].years << " "
<< candidates[i].fortune << "\n";
}
}
}
return 0;
}방법 2: 효율적인 선형 탐색 (통과 가능)
실제로는 전체를 자산순으로 정렬 후, 각 질의마다 선형 탐색하되 조기 종료를 활용하면 통과할 수 있습니다. 핵심은 ios::sync_with_stdio(false)와 cin.tie(nullptr)로 입출력 최적화하는 것입니다.
#include <bits/stdc++.h>
using namespace std;
struct Entity {
string label;
int lifetime;
int assets;
};
bool priorityOrder(const Entity& first, const Entity& second) {
if (first.assets != second.assets)
return first.assets > second.assets;
if (first.lifetime != second.lifetime)
return first.lifetime < second.lifetime;
return first.label < second.label;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int population, questionCount;
cin >> population >> questionCount;
vector<Entity> records(population);
for (int idx = 0; idx < population; idx++) {
cin >> records[idx].label >> records[idx].lifetime >> records[idx].assets;
}
sort(records.begin(), records.end(), priorityOrder);
for (int qIdx = 1; qIdx <= questionCount; qIdx++) {
int maxDisplay, ageLower, ageUpper;
cin >> maxDisplay >> ageLower >> ageUpper;
cout << "Case #" << qIdx << ":\n";
int found = 0;
for (const auto& entry : records) {
if (found >= maxDisplay) break;
if (entry.lifetime >= ageLower && entry.lifetime <= ageUpper) {
cout << entry.label << " "
<< entry.lifetime << " "
<< entry.assets << "\n";
found++;
}
}
if (found == 0) {
cout << "None\n";
}
}
return 0;
}주의사항
printf/scanf대신cin/cout을 쓸 때는 반드시 입출력 동기화를 끄세요- 벡터의
insert는 O(n)이므로 범위 삽입 시 주의 - 각 연령당 최대 100명만 저장하는 최적화도 고려 가능