알고리즘 - BOJ 10814 나이순 정렬 - Tue, Sep 29, 2020
cpp에서 stable_sort()는 안정 정렬이다.
BOJ
BOJ 10814 나이순 정렬 문제는 간단한 정렬문제이다.
다만 기본 정렬인 퀵정렬은 불안전 정렬이기 때문에 안정정렬을 사용해야 한다.
실패 분석
- 출력이 많은데 endl을 사용하면 시간초과가 발생한다.
- 그 사실을 모르고 복잡도 때문인지 알고 카운팅 소트를 구현해서 사용했다.
안정 정렬 구현 코드
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using i64 = long long int;
struct People {
int age;
string name;
};
bool cmp(const People &a, const People &b) {
return a.age < b.age;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <People> a(n);
for (int i = 0; i < n; i++) {
People p;
cin >> p.age >> p.name;
a[i] = p;
}
stable_sort(a.begin(), a.end(), cmp);
for (int i = 0; i < n; i++) {
cout << a[i].age << " " << a[i].name << '\n';
}
return 0;
}%
카운팅 소트 구현 코드
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using i64 = long long int;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <vector <string>> v(201);
for (int i = 0; i < n; i++) {
int age;
string name;
cin >> age >> name;
v[age].push_back(name);
}
for (int i = 1; i <= 200; i++) {
if (v[i].size() != 0) {
for (auto &name: v[i]) {
cout << i << " " << name << "\n";
}
}
}
return 0;
}
난이도
- 체감 난이도 2점. 쉬운 편이다.
- BOJ 난이도: 실버 5. 쉬운 편