💻 10814번 문제 : 나이순 정렬 📕🙋

Buᐢ༝ᐢy 2022. 12. 1. 06:00

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

struct Member
{
	int age = 0;
	string name = "";
};

bool compare(const Member& p_memberA, const Member& p_memberB)
{
	return p_memberA.age < p_memberB.age;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N = 0;
	cin >> N;
	Member members[100000];

	for (int i = 0; i < N; i++)
	{
		cin >> members[i].age >> members[i].name;
	}

	stable_sort(members, members + N, compare);

	for (int i = 0; i < N; i++)
	{
		cout << members[i].age << ' ' << members[i].name << '\n';
	}
}

메모리 (KB)	시간 (ms)	코드 길이 (B)
7772	44	577

이전에 풀던 방식처럼 vector<pair<int, string>> memberV 로도 풀었지만 시간을 단축하고 싶어서 여러 가지 방법을 시도해보았다. 문제를 처음 봤을 때 구조체를 쓰고 싶었으나 풀던 당시에는 당장 어떻게 풀어야 하나 감이 잡히지 않아서 기존 방법처럼 풀었다. 생각할 여유가 생기고 구조체로 풀어보았는데 시간이 줄어서 좋다.

📕 오답 노트

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

bool compare(pair<int, string> pairA, pair<int, string> pairB)
{
    return pairA.first < pairB.first;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N = 0;
    cin >> N;
    
    vector<pair<int, string>> memberV;
    
    for(int i = 0; i < N; i++)
    {
        int age = 0;
        string name;
        
        cin >> age >> name;
        
        memberV.push_back(make_pair(age, name));
    }
    
    sort(memberV.begin(), memberV.end(), compare); // 이 한 줄 때문에 몇 번이고 틀렸던 것이다!
    
    for(int i  = 0; i < N; i++)
    {
        cout << memberV[i].first << ' ' << memberV[i].second << '\n';
    }
}

비주얼 스튜디오에서는 출력 예시처럼 잘 나왔고, 다른 예시들도 잘 나왔었다. 그래서 도무지 이해가 가지 않아 여러 가지 생각을 하다가 sort()처럼 정렬 기능이 있지만 순서를 확실히 해주는 함수가 있다는 것을 알았다. 바로 stable_sort()이다. 바로 밑에서 간단하게 알아보려고 한다.

🙋 더 알아보기

sort()와 stable_sort() 두 함수는 정렬한다는 기능은 같다. 다른 점이 있다면, 이 문제처럼 pair<int, string>를 비교한다고 가정해보자. string은 신경 쓰지 않고 각 int만 오름차순 혹은 내림차순으로 하고 싶을 때 sort()는 순서를 확정할 수 없다. 그래서 int가 서로 다를 때 정렬을 시키고 int가 같다면 string은 vector 순서 그대로 사용할 수 있다.

정리하자면,

순서가 보장된 정렬을 사용하고 싶다! → stable_sort();

순서로 범위의 요소를 정렬하고 동등한 요소의 순서는 보존되도록 보장됨.

std::stable_sort

Sorts the elements in the range [first, last) in non-descending order. The order of equivalent elements is guaranteed to be preserved. 1) Elements are compared using operator<. 3) Elements are compared using the given comparison function comp. 2,4) Same as (1,3), but executed according to policy.

https://en.cppreference.com/w/cpp/algorithm/stable_sort