알고리즘 - C++의 set 정렬 기준을 임의로 바꾸기 & 백준 단어정렬

C++의 set 정렬 기준을 임의로 바꾸기

기본적으로 C++의 STL 중 set 은 원소를 넣을 때마다 자동적으로 오름차순 정렬되어 들어갑니다.

하지만 원소를 넣을 때 정렬되는 기준을 사용자 마음대로 바꾸고 싶을 경우가 생길 수 있습니다.

먼저, set의 템플릿을 살펴볼 필요가 있습니다. set이 정의된 소스 코드를 살펴 보겠습니다.

1
2

// CLASS TEMPLATE set
template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>

맨 첫번째 인자는 type 명이 들어가는 곳이고, 두 번째 인자에 주목해야 합니다.

_Pr 부분이 바로 비교 함수가 들어가는 곳입니다. 여기에 default로 less, 즉 기본적으로 오름차순 정렬되도록 들어가 있던 것입니다.

그러면 이 less 를 살펴볼 필요가 있습니다.

1
2
3
4
5
6
7
8
9
10

template <class _Ty = void>
struct less {
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty first_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef _Ty second_argument_type;
    _CXX17_DEPRECATE_ADAPTOR_TYPEDEFS typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const {
        return _Left < _Right;
    }
};

이로부터 less는 구조체 형태이고, 안에 operator() 가 연산자 오버로딩되어 있음을 알 수 있습니다.

그리고 그 안에는 오름차순으로 정렬되도록 하는 코드가 들어가 있습니다.

따라서 두 번째 인자에 들어갈 것은 기본적으로 “구조체 형태” 여야 하고, “operator() 연산자 오버로딩” 하면 됩니다.

정렬 기준을 바꾸고 싶으면, 두 번째 인자에 들어갈 것을 직접 구현하여 아래와 같이 넣으면 됩니다.

1

set<int, compare> sets; // compare라는 임의의 구조체 안에 비교함수를 선언

백준 1181번 - 단어 정렬

문제 바로가기 : https://www.acmicpc.net/problem/1181

[조건] 알파벳 소문자로 이루어진 N개의 단어가 들어오면,

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

정렬하여 출력하는 문제입니다.

단, 3. 같은 단어가 여러 번 입력되었을 때는, 출력 시 한 개만 출력해야 합니다.

이 문제를 예시로 든 이유는, set을 활용하면 간단하면서도 실행 시간을 획기적으로 낮출 수 있기 때문입니다.

우선 set에 모든 문자열들을 넣어 두고, 그 안의 원소들을 정렬하는 접근법을 생각할 수 있습니다.

일단, set에 자료를 저장하므로 3번 조건은 바로 해결됩니다.

set의 기본적인 성질에 의하여 중복되는 단어들은 피해지고 한 개씩 insert될 것이기 때문입니다.

그런데 set은 오름차순 정렬이 default 이므로, set에 위와 같이 문자열들을 모두 넣는다면 사전 순으로 정렬되어 있겠지만, 1번 단어의 길이 조건은 고려되지 못한 채 들어가 있는 것입니다.

따라서 중복되는 단어들을 쉽게 제거할 수 있는 set을 활용하되, 정렬 기준만 바꾼 다음 set에 들어가 있는 모든 원소를 차례대로 출력만 하면 이 문제의 답이 될 것입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <set>

using namespace std;

// set 의 정렬 기준을 바꾸기 위한 구조체 Compare 정의
struct Compare {
	bool operator() (const string &a, const string &b) const{
		if (a.size() == b.size())
			return a < b;
		else
			return a.size() < b.size();
	}
};

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
    
	int N;
	set<string, Compare> sets; // 이와 같이 선언
	cin >> N;
	string temp;

	for (int i = 0; i < N; i++) {
		cin >> temp;
		sets.insert(temp);
	}

	for (auto str : sets) {
		cout << str << '\n';
	}

	return 0;
}

• 벡터를 활용하여 매번 중복 원소가 없는지 체크한 뒤 push 한 다음, 마지막에 일괄 정렬하는 알고리즘은 약 1200ms의 실행 시간을 보였습니다.
• 그러나 위처럼 set을 활용하면 매번 체크할 필요 없이 set이 자동적으로 해 주기 때문에 실행 시간이 24ms 정도로 거의 50배 가량 개선되었음을 확인하였습니다.