단어 정렬 (feat. 백준, 1181번)

단어 정렬
https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1181
#include <iostream>
#include <string>
#include <set>
using namespace std;
struct cmp {
	bool operator() (const string& v1, const string& v2) const {
		if (v1.size() == v2.size())
			return v1 < v2;
		return v1.size() < v2.size();
	}
};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	string tmp;
	set<string, cmp> ans;
	cin >> N;
	for (register int i = 0; i < N; ++i)
		cin >> tmp, ans.insert(tmp);
	for (auto iter = ans.begin(); iter != ans.end(); ++iter)
		cout << *iter << "\n";
	return 0;
}
// *&)*@*

문제에서 주어진 조건 "문자열의 길이가 짧은 것부터, 문자열의 길이가 같으면 사전 순으로, 같은 문자열은 하나만 출력한다" 입니다.

자료구조 중 set은 map과 같이 key를 갖는 자료구조이며 중복된 key는 무시됩니다. 단, map과 같이 value를 입력할 순 없습니다.

주어진 문제는 map<string, 아무거나> 의 자료형을 사용하면 보다 쉽게 해결할 수 있습니다.

map의 key는 문제의 조건으로 입력과 동시에 정렬되기 때문입니다.

set의 경우, 자료형을 선언할때 predicate를 설정할 수 있습니다. 다만 sort와 같이 리턴형이 bool인 함수가 아닌, operator()에 의해서 설정됩니다.

set 자료형이 어떻게 정의되어 있는지 확인해보겠습니다.

자료형 set의 원형

여기서 _Pr이 바로 predicate입니다. 원형은 less<_Kty>로 정의되어 있네요. 그럼 less는 어떻게 생겼는지 확인해보겠습니다.

less의 원형

operator()를 오버로딩한 구조체 입니다.

따라서 사용자가 _Pr 즉, predicate를 정의한다면 operator()를 오버로딩한 구조체여야 하고 정렬 기준은 operator()를 어떻게 구현하는가에 따라 다를 것입니다.