[코딩테스트 35일차] BAEKJOON 10814번 : 나이순 정렬

[BAEKJOON 10814번 : 나이순 정렬]

[문제]

---

[고찰]

저는 이 문제를 어떻게 풀지 고민할 때, pair 클래스는 sort를 적용할 때, 자동으로 second 요소까지 자동으로 정렬을 적용한다는 것을 생각하였습니다.

 

그래서 sort를 사용하는 것은 안되겠다 하여, 직접 정렬을 구현하였습니다.

어떻게 구현할지 많은 고민 끝에, 비효율적인 것을 알지만서도 방법이 없어 아래와 같이 구현하였습니다.

 

무한 루프 안에서, 제대로 정렬이 될 때까지 계속 입력받은 벡터를 반복하는 형태로 구현하였습니다.

#include <iostream>
#include <vector>     // 10814번

using namespace std;

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

	int n;
	cin >> n;

	pair<int, string> p;
	vector<pair<int, string>> subscriber;
	bool bIsSort = false;

	while (n--)
	{
		cin >> p.first >> p.second;
		subscriber.push_back(p);
	}

	while (true)
	{
		int i = 0;
		bIsSort = false;

		for (i; i < subscriber.size(); i++)
		{
			if (i + 1 >= subscriber.size())
				break;

			if (subscriber[i].first == subscriber[i + 1].first)
				continue;

			if (subscriber[i].first > subscriber[i + 1].first)
			{
				swap(subscriber[i], subscriber[i + 1]);

				bIsSort = true;
			}
		}

		if (!bIsSort)
		{
			break;
		}
	}

	for (const auto& p : subscriber)
	{
		cout << p.first << ' ' << p.second << '\n';
	}

	return 0;
}

 

물론 위의 작성된 코드로, 시간 초과가 뜨면서 실패하였습니다.

 

다른 분들의 풀이를 보니, 해당 문제를 풀 수 있는 간단한 방법이 존재하였습니다.

그 간단한 방법은 stable_sort() 함수였습니다.

 

또한, 구조체를 사용하는 방법도 있었습니다.

나이와 이름, 그리고 입력 순서를 저장할 수 있는 구조체를 만들고, 이 구조체를 기반으로 벡터를 만들어서 sort를 적용했어도 됩니다.

 

입력 순서를 저장하는 방법도 생각을 못한건 아니지만, pair 클래스에만 생각이 갇혀있어 구조체를 생각하지 못했습니다.

 

그래서 stable_sort( )와 구조체를 활용하는 풀이에 대해 정리하고자 합니다.

---

[개념]

제가 푼 코드는 시간 복잡도가 O(n²)로 매우 비효율적입니다. 

이를 개선하기 위해서 stable_sort( )를 사용하는 방법과, 구조체를 사용하는 방법에 대해 정리합니다.

 

stable_sort

#include <algorithm>

template <class RandomIt, class Compare>
void stable_sort(RandomIt first, RandomIt last, Compare comp);

 

stable_sort는 정렬 시, 원래의 순서를 보장해주는 정렬 함수입니다.

sort와 사용법은 동일하지만, sort와는 달리 정렬 기준이 동일한 요소끼리는 원래의 입력 순서를 유지합니다.

 

stable_sort를 사용할 시 시간 복잡도는 최악의 경우 O(n log² n)이며, 평균적으로는 O(n log n)의 시간 복잡도를 갖습니다.

 

struct 사용

나이와 이름, 입력 순서를 저장할 수 있는 구조체를 만듭니다.

struct Person
{
    int age;
    string name;
    int order;
}

 

이후 boolean을 반환형으로 하는 comapre 함수를 만들어, Person a와 Person b를 비교할 수 있게 합니다.

---

[정리]

몰랐던 개념인 것도 있었지만, 충분히 풀 수 있었던 문제라고 생각합니다.

코딩테스트에서 생각의 틀이 갇히는 것만큼 위험한 것은 없는 것 같다고 느꼈고, 생각의 틀에 갇히지 않게 조심해야 겠습니다.

---

[Solution : stable_sort 활용]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(const pair<int, string>& a, const pair<int, string>& b)
{
	return a.first < b.first;
}

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

	int n;
	cin >> n;

	vector<pair<int, string>> members(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> members[i].first >> members[i].second;
	}

	stable_sort(members.begin(), members.end(), compare);

	for (const auto& member : members)
	{
		cout << member.first << " " << member.second << '\n';
	}

	return 0;
}

 

---

[Solution : struct 활용]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct Person
{
    int age;
    string name;
    int order;
};

bool compare(const Person& a, const Person& b)
{
    if (a.age == b.age)
        return a.order < b.order;
        
    return a.age < b.age;
}

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

    int n;
    cin >> n;

    vector<Person> people(n);

    for (int i = 0; i < n; i++)
    {
        cin >> people[i].age >> people[i].name;
        people[i].order = i;
    }

    sort(people.begin(), people.end(), compare);

    for (const auto& person : people)
    {
        cout << person.age << ' ' << person.name << '\n';
    }

    return 0;
}