백준 10814번 문제 c++ 풀이#

문제#

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력#

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력#

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1#

입력:
3 21 Junkyu
21 Dohyun
20 Sunyoung

출력:
20 Sunyoung
21 Junkyu
21 Dohyun

아이디어#

힙 자료구조, C++ STL에서는 우선순위 큐를 이용한다.
C++ STL의 priority_queue는 최대 힙(max heap)을 사용하기 때문에 최소 힙으로 만드는 `greater<>를 사용한다.
같은 나이는 넣은 순서대로 나와야하니 넣은 순서도 저장할 때 같이 저장한다.
힙에 차례대로 넣고 차례대로 빼서 출력한다.

1차 시도#

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int N, M;
priority_queue<pair<int, pair<int, string>>,
               vector<pair<int, pair<int, string>>>,
               greater<pair<int, pair<int, string>>>>
    container;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        int x;
        string y;
        cin >> x >> y;
        container.push(make_pair(x, make_pair(i, y)));
    }
    for (int i = 0; i < N; ++i)
    {
        cout << container.top().first << " " << container.top().second.second
             << "\n";
        container.pop();
    }
}

결과
맞았습니다!!

1차 시도 Comment#

먼저 넣은 순서대로 먼저 나오게 하기위해 priority_queue의 비교함수에 대해 추가적으로 공부했습니다. priority_queue의 비교함수는 기존 값이 2번째 인자로 새로운 값이 첫번째 인자로 들어가고 true를 반환하면 1번째 인자의 우선순위가 낮고 반대는 두번째 인자의 우선순위가 낮도록 설계되어 있었습니다. 추가적으로 비교함수는 operator()를 오버로딩해서 만들어야하고 a < a는 무조건 false를 반환, a < b, b < a가 같은 결과가 나오면 안되도록하는 조건이 있었습니다.

깃헙 링크 : link