[C/C++] 백준 1181번 - 단어 정렬 (std::sort, std::unique, std::erase)

 

<코드>

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

bool compare(string a, string b) {
	if (a.size() == b.size()) { // 글자수가 같을 경우 사전순으로 배치
		return a < b;
	}
	else { // 글자수 다를 경우 짧은 순으로 배치
		return a.size() < b.size();
	}
}

int main()
{
	int n;
	string s;
	vector<string> v;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> s;
		v.push_back(s);
	}

	sort(v.begin(), v.end(), compare); // 정렬
	v.erase(unique(v.begin(), v.end()), v.end()); // vector 배열에서 중복되지 않는 원소들을 앞에서부터 채우고 필요한 부분만 남긴다.

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}

	return 0;
}

 

 

문자열을 비교하기 때문에 algorithm 헤더 파일에 있는 sort함수를 사용하고, 이때 sort함수의 3번째 인자에 사용자 정의 함수 compare함수를 따로 만들어서 인수로 string형 변수 a와 b를 받아

sort(v.begin(), v.end(), compare); // 정렬

 

1. a와 b의 글자 수가 같을 경우 사전 순으로 정렬하고

if (a.size() == b.size()) { // 글자수가 같을 경우 사전순으로 배치
		return a < b;
}

2. 글자 수가 다를 경우 짧은 글자 순으로 정렬을 한다.  

else { // 글자수 다를 경우 짧은 순으로 배치
	return a.size() < b.size();
}

 

unique함수는 vector 배열에서 중복되지 않는 원소들을 앞에서부터 채워나간다. 그렇다면 앞부분부터 원소들이 변경될 것이고 뒷부분에는 변경이 되지 않은 원소들이 남아있는데 그 부분이 시작되는 주소를 반환한다.

(만약 sort가 안된 배열에서 unique함수를 사용 시, 사용자의 의도대로 동작하지 않는다.)

unique(v.begin(), v.end()); // vector 배열에서 중복되지 않는 원소들을 앞에서부터 채움

만약 1,2,2,3,3,3,4,5,5,6이라는 입력이 있을 때 중복된 원소들을 제외하면 1,2,3,4,5,6이며 이 원소들을 vector 배열의 앞부분부터 채운다.

1,2,3,4,5,6,4,5,5,6 

그리고 unique함수는 변경되지 않은 7번째 원소의 주소를 반환하게 된다.

 

그리고 erase함수를 통해  vector 배열의 변경되지 않은 뒷부분(7번째 원소)부터 끝부분까지 잘라낸다.

v.erase(unique(v.begin(), v.end()), v.end());

 

이처럼 vector 배열의 중복된 원소를 제거할 때는 sort+unique+erase 함수 3가지 조합을 이용하여 처리할 수 있다. 

 

www.acmicpc.net/problem/1181

1181번: 단어 정렬