백준 1181번 : 단어 정렬

문자열 중복 확인은 set으로, 정렬은 priority_queue로 해결했다. 다른 문제는 대부분 세자릿수 ms를 기록한 것과 비교해 68ms의 매우 빠른 속도로 문제를 푼 것을 확인할 수 있다.
근데 사실 priority_queue 안쓰고 퀵소트 하는게 속도가 조금 더 빠르다. 삽입 O(Log N) + 검색 O(1) + 삭제 O(Log N) 와 삽입O(1) + 정렬 O(Log N) + 검색 O(1) 차이다.

//우선순위 큐 버전
#include <iostream>
#include <queue>
#include <set>
#include <string>

using namespace std;

struct GreaterString
{
	bool operator()(const string& a, const string& b)
	{
		int aLength = a.length();
		int bLength = b.length();
		if (aLength == bLength)
		{
			return a > b;
		}

		return aLength > bLength;
	}
};

int main()
{
	int N;
	scanf("%d", &N);
	cin.ignore();

	set<string> inputs;
	priority_queue<string, vector<string>, GreaterString> strs;
	for (int i = 0; i < N; i++)
	{
		string str;
		getline(cin, str);
		if (inputs.find(str) == inputs.end())
		{
			inputs.insert(str);
			strs.push(str);
		}
	}

	while (!strs.empty())
	{
		printf("%s\n", strs.top().c_str());
		strs.pop();
	}
	
	return 0;
}

//퀵소트 버전
#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

bool customPair(const string& a, const string& b)
{
	int aLength = a.length();
	int bLength = b.length();
	if (aLength == bLength)
	{
		return a < b;
	}

	return aLength < bLength;
}

int main()
{
	int N;
	scanf("%d", &N);
	cin.ignore();

	set<string> inputs;
	vector<string> strs;
	for (int i = 0; i < N; i++)
	{
		string str;
		getline(cin, str);
		if (inputs.find(str) == inputs.end())
		{
			inputs.insert(str);
			strs.push_back(str);
		}
	}

	sort(strs.begin(), strs.end(), customPair);

	for (string str : strs)
	{
		printf("%s\n", str.c_str());
	}
	
	return 0;
}