[C++] 백준 1181 : 단어 정렬

 

 

 

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

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

 

 

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

 

 

 

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

 

 

---

 

 

문제 해결

문제에서 주어진 조건대로 두 가지 비교 함수를 이용하여 정렬을 해야한다.

 

 

하나는 단어의 길이, 다른 하나는 단어의 사전 순이다. 알파벳의 순서에 관계없이 무조건 짧은 단어가 긴 단어보다 앞에 위치해야하므로 먼저 단어의 길이를 기준으로 전체 정렬을 수행한다.

 

 

그런 다음 같은 길이의 단어들을 알파벳 순으로 사전식 정렬을 수행해야 한다. 반복을 수행하면서 다음 단어와 그 직전 단어의 길이가 다른 지점 j를 정렬의 시작점으로, 인덱스 j인 단어의 길이와 달라지는 지점 i를 정렬의 끝지점으로 두고 오름차순 정렬을 수행하면 된다. ( j ≤ i )

 

 

이 때 주의해야 할 점이 sort(v.begin(), v.end(), compare) 함수의 정렬 범위는 [begin, end)라는 것이다. 예를 들어 v[3]부터 v[6]까지 정렬하고 싶다면, sort(v + 3, v + 6, compare)이 아니라 sort(v + 3, v + 7, compare)로 수행해야 한다. 따라서 반복문의 i는 n 미만이 아닌 n 이하로 범위를 설정해야 한다.

 

 

마지막으로 중복된 단어를 한 번씩만 출력하기 위해, 현재 단어와 다음 단어가 같은 경우 continue문이 실행되도록 한다.

 

 

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

string ary[20001];
int n;

bool compare_length(string a, string b) {
	if (a.size() < b.size()) return true;
	return false;
}

int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> ary[i];

	sort(ary, ary + n, compare_length);		// 먼저 길이 기준으로 정렬

	for (int i = 0, j = 0; i <= n; i++)		// sort 함수의 두 번째 인자 때문에 i가 n까지 올라가도록 설정
		if (ary[i].size() != ary[j].size()) {
			sort(ary + j, ary + i);
			j = i;
		}


	for (int i = 0; i < n; i++) {
		if (ary[i] == ary[i + 1]) continue;
		cout << ary[i] << '\n';
	}
}