[BOJ] 10814 나이순 정렬
💡 문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.
💻 입력
첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.
💻 출력
첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.
🤔 내가 생각한 로직 이라고 쓰고 삽질이라 읽는다
일단 처음 생각한 것은 그냥 sort()함수를 커스터마이징해서 쓰면 되는 것 아닌가? 라고 생각했었다. 그리고 장렬하게 틀렸다.(ㅎ...)
나는 sort()함수가 커스터마이징한 함수의 기준에서 두개가 같다면 입력 순서대로 출력해주는 줄 알았는데, 그런 보장은 없다고 한다.
그래서 입력한 순서대로 출력을 보장해주는 게 뭘까.. 싶다가 선입선출인 큐를 이용하되, 우선순위가 있으니까 priority queue 를 이용하는 걸까? 싶어서 맨 첫번째 풀이는 우선순위 큐를 이용해서 풀어보았다.
✔️ 우선순위 큐를 이용한 풀이
코드 하나하나씩 step-by-step 으로 뜯어보도록 하겠다.
☝️ STEP 1
typedef struct {
int age;
string name;
int no;
}person;나이, 이름, 우선순위(들어온 순서)를 담고 있는 person 구조체를 선언한다.
✌️ STEP 2
struct cmp {
bool operator() (person a, person b) {
if(a.age > b.age) return true;
else if(a.age == b.age) {
if(a.no > b.no) return true;
else return false;
}
return false;
}
};커스터마이징할 cmp클래스(연산자를 담고 있는)를 꾸며준다.
이 cmp클래스는 operator메서드를 담고 있는데, operator 연산자는
파라미터로 2개의 person 구조체를 받아서, 나이가 적→큰 순서대로 나열하고, 나이가 같다면 우선순위 no가 적→큰 순서대로 나열해준다.
👌 STEP 3
priority_queue <[Data Type], [Container Type]> [변수이름];
을 지켜서 우선순위 큐를 선언해준다. 이때 Data Type은 person구조체이고, 정렬할 것을 담을 vector을 Container Type으로 선언해준다.
priority_queue<person, vector<person>, cmp> pq;💻 전체 코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef struct {
int age;
string name;
int no;
}person;
struct cmp {
bool operator() (person a, person b) {
if(a.age > b.age) return true;
else if(a.age == b.age) {
if(a.no > b.no) return true;
else return false;
}
return false;
}
};
int n;
priority_queue<person, vector<person>, cmp> pq;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
person temp;
for(int i = 0; i < n; i++) {
cin >> temp.age >> temp.name;
temp.no = i;
pq.push(temp);
}
for(int i = 0; i < n; i++) {
cout << pq.top().age << " " << pq.top().name << "\n";
pq.pop();
}
return 0;
}오랜만에 구조체랑 커스텀 함수를 쓰느라고 진땀을 쭉쭉 뺐다...🥲
근데 더 찾아보니까, 이렇게 말고도 C++은 '안정 정렬'이라는 stable_sort()함수를 제공한다고 한다! 🤣🤣
이 stable_sort()함수는 커스텀 함수대로 정렬하되, 출력 시 입력한 순서대로 정렬 순서를 자동적으로 보장해준다고 한다.
✔️ stable_sort()를 이용한 풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<pair<int, string>> v;
bool cmp(pair<int, string> a, pair<int, string> b){
return a.first < b.first;
}// 나이가 적은 순서대로 정렬해주는 함수
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
while(n--) {
int no;
string name;
cin >> no >> name;
v.push_back({no, name});
}
//stable_sort: cmp대로 정렬하되, vector에 삽입한 순서는 지키게 되는 함수
stable_sort(v.begin(), v.end(), cmp);
for(auto x: v) {
cout << x.first << " " << x.second << "\n";
}
}