[백준알고리즘] 1181번: 단어 정렬 -C++

[백준알고리즘] 1181번: 단어 정렬 -C++

1181번: 단어 정렬 (acmicpc.net)

1181번: 단어 정렬

 

입력으로 \(n\)개의 단어들이 들어올 때 세 가지 조건에 맞춰서 입력된 단어들을 출력하면 된다.

1. 단어들 중 단어의 길이가 짧은 것부터 긴 것까지, 단어의 길이의 오름차순
2. 단어의 길이가 같다면, 사전 순 (단어의 오름차순)
3. 중복된 입력의 단어는 삭제

---

 

메모리와 시간 조건이 넉넉하니 정렬이야 sort를 사용해서 해주었다.

여기서 직접 비교 함수를 만들어서 넣어주어도 되지만, 나는 입력을 받을 때 pair로 저장했다.

 

pair는 입력한 문자열의 길이와 입력한 문자열을 함께 묶어주었다.

그리고 이 vector를 less<>에 의한 오름차순 정렬을 시켜줌으로써, pair의 첫 번째 인자인 단어의 길이로 먼저 오름차순 정렬이 되었고 다음으로 두 번째 인자인 단어의 사전 순으로 오름차순 정렬이 되었다.

 

즉, 위의 출력 조건 세 가지 중 두 가지를 한 번에 만족시켰다.

 

---

 

다음으로 중복된 단어의 처리가 필요했다.

따라서 <algorithm> 헤더에서 제공하는 unique 함수와 <vector> 에서 제공하는 erase를 사용했다.

 

unique 함수의 경우에는 중복되는 값을 vector의 맨 뒤로 이동시킨다. 

예를 들어서 {1, 1, 1, 2, 2, 3, 4, 5, 6}의 벡터가 존재한다면, unique 함수를 이용하면 {1, 2, 3, 4, 5, 6, 1, 1, 2}로 되는 것이다.

 

따라서 뒤로 보낸 중복 값을

그렇기 때문에 erase를 사용해서 뒤로 미뤄진 중복 값을 제거했다. 

 

unique 함수의 return value는 중복 값을 뒤로 미룬 후 시작하는 첫 번째를 가리키는 iterator이기 때문에, 해당 값을 그대로 erase 함수의 첫 번째 인자로 넣어주었다.

 

중복을 제거하기 위해 unique와 erase를 사용하는 방법에 대해서는 아래 블로그 주소를 참고해서 풀었다.

코딩벌레 :: [C++]벡터 중복제거(sort,unique,erase) (tistory.com)

 

---

아래는 C++ 코드다.

#include <iostream>
#include <algorithm>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<std::pair<int, std::string>> dictionary;
	for (int i = 0; i < n; i++)
	{
		std::string str;
		std::cin >> str;
		dictionary.push_back(std::make_pair(str.length(), str));
	}

	std::sort(dictionary.begin(), dictionary.end());
	dictionary.erase(std::unique(dictionary.begin(), dictionary.end()), dictionary.end());

	for (int i = 0; i < dictionary.size(); i++)
		std::cout << dictionary[i].second << '\n';
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다