백준-10814(나이순 정렬) C++
https://www.acmicpc.net/problem/10814
10814번: 나이순 정렬
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을
www.acmicpc.net
처음 문제를 접했을 때 떠오른 방법은 이중 배열이었다. 하지만 입력되는 정보들은 정수형과 문자열이다. (물론 나이를 먼저 문자열로 받고, 나중에 정수형으로 바꿀 수도 있겠지만 잘 모르는 상태...)
그래서 떠오른 방법은 pair을 사용하는 것이었다. 아직 사용법을 잘 몰라 구글링을 하면서 익혔다. (입출력, 선언 등...)
vector에 pair을 적용시키는 방향으로 코드를 작성하였다.
다 입력받은 후에는 sort 내장 함수를 사용하니 예시 결과가 잘 나와 당연히 통과될 줄 알았다....
하지만 결과는....
결국 구글에 문제를 직접 검색하였다.... 그래서 알아낸 것은 sort가 아닌 stable_sort를 사용하면 정답이 된다는 정보를 얻었다.
이 둘의 차이점을 알아보자.
- sort(불안정 정렬): 동일한 값에 순서가 바뀔 수 있다.
- stable_sort(안정 정렬): 동일한 값에 순서가 바뀌지 않는다.
이 문제가 나이가 같을 경우에는 알파벳 순이 아닌, 먼저 가입한 사람이 출력되도록 해야 한다.
stable_sort를 사용했을 때 순서가 바뀌지 않고, 입력한 순서대로 출력하도록 설정 가능한 것 같다.
더불어 pair가 <나이, 이름>으로 구성되어 있는데 나이만 이용해 정렬하기 위해 compare함수를 넣어 stable_sort에 적용시켰다.
(마지막에 코드가 나오니 이를 확인하자.)
그래서 확신에 찬 마음으로 채점을 돌렸더니....
시간 초과가 발생해버렸다....
iostream의 cin, cout이 scanf, printf보다 느리다는 것을 알고 있었지만, 나는 string을 받았기 때문에 cin, cout을 사용할 수밖에 없었다...
그래서 내가 할 수 있는 최선의 방법은 endl을 "\n"으로 바꿔 실행할 경우의 수만 남아 이를 실행하였더니...
이게 성공이었다ㅋㅋㅋㅋㅋㅋㅋ
endl 이 하나가 문제의 성공을 좌우할 줄은 상상도 못 했다....
마지막으로 전체 코드다.
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
bool compare(pair<int, string> a, pair<int, string> b)
{
return a.first < b.first;
}
int main()
{
// freopen("input.txt", "rt", stdin);
int n;
scanf("%d", &n);
vector<pair<int, string>> vec(n);
for (int i = 0; i < n; i++)
{
cin >> vec[i].first >> vec[i].second;
}
stable_sort(vec.begin(), vec.end(), compare);
for (int i = 0; i < n; i++)
{
cout << vec[i].first << " " << vec[i].second << "\n";
}
return 0;
}