백준-10814(나이순 정렬) C++

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

처음 문제를 접했을 때 떠오른 방법은 이중 배열이었다. 하지만 입력되는 정보들은 정수형과 문자열이다. (물론 나이를 먼저 문자열로 받고, 나중에 정수형으로 바꿀 수도 있겠지만 잘 모르는 상태...)

 

그래서 떠오른 방법은 pair을 사용하는 것이었다. 아직 사용법을 잘 몰라 구글링을 하면서 익혔다. (입출력, 선언 등...)

vector에 pair을 적용시키는 방향으로 코드를 작성하였다.

다 입력받은 후에는 sort 내장 함수를 사용하니 예시 결과가 잘 나와 당연히 통과될 줄 알았다....

하지만 결과는....

 

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;
}