[Algorithm][BOJ][1181] 단어 정렬

단어 정렬

1. 요구사항 분석
2. 알고리즘 선택
3. 풀이 분석
4. 최적화

요구사항 분석

N개의 단어들을 2가지의 정렬 방법에 따라 정렬 후 출력하는 문제입니다.

1. 단어의 길이를 오름차순으로 정렬합니다.
2. 같은 길이의 단어는 사전순으로 정렬합니다. (동일한 단어는 1회만 출력합니다.)
   

위의 정렬 방법을 지켜 단어를 정렬하되
단어의 수는 20,000개 이하이고 각 단어의 길이은 50을 넘기지 않습니다.

올라가기

알고리즘 선택

단어들의 중복을 허용하지 않고 정렬을 진행해야 하므로 set 라이브러리를 사용합니다.
set은 기본적으로 원소에 대해 오름차순 정렬을 시행합니다.
그러나 내림차순 혹은 다른 정렬을 사용하고 싶을 경우, set의 선언과 함께
정렬 방법을 함께 적시해두면 해당 방법으로 정렬되도록 할 수 있습니다.

올라가기

풀이 분석

WORD_ORDER 라는 새로운 정렬 방법을 만들고
set을 선언할 때 원소의 자료형 다음으로 정렬 방법을 알려줍니다.

#include <iostream>
#include <set>

struct WORD_ORDER {
	bool operator() (const std::string& lhs, const std::string& rhs) const
	{
		if (lhs.size() < rhs.size()) {
			return true;
		}
		else if (lhs.size() > rhs.size()) {
			return false;
		}

		for (int i = 0; i < lhs.size(); ++i) {
			if (lhs[i] == rhs[i]) continue;
			return lhs[i] < rhs[i];
		}
		return false;
	}
};

int main() {
	int N;
	std::cin >> N;
	std::set<std::string, WORD_ORDER> set;
	for (int i = 0; i < N; ++i) {
		std::string buf;
		std::cin >> buf;
		set.insert(buf);
	}
	
	for (auto s : set)
		std::cout << s << std::endl;
	return 0;
}   
   

올라가기

최적화

std::string 자료형은 내장 비교연산자가 존재하며 해당 비교연산자는 사전순으로 정렬됩니다.
이를 이용하여 더 효율적인 코드를 작성할 수 있습니다.

#include <iostream>
#include <set>

struct WORD_ORDER {
	bool operator() (const std::string& lhs, const std::string& rhs) const
	{
		if(lhs.size() == rhs.size())
			return lhs < rhs;
		else
			return lhs.size() < rhs.size();
	}
};

int main() {
	int N;
	std::cin >> N;
	std::set<std::string, WORD_ORDER> set;
	for (int i = 0; i < N; ++i) {
		std::string buf;
		std::cin >> buf;
		set.insert(buf);
	}
	
	for (auto s : set)
		std::cout << s << std::endl;
	return 0;
}   
   

올라가기