정렬. [20920]

[1. 문제 설명]

https://www.acmicpc.net/problem/20920

---

[2. 풀이 접근]

기본적인 접근

• 중복된 단어를 체크할 때, multiset 이나 map 을 이용해서 카운트
• multiset 보다는 map 을 이용하는게 나을지도,
• key 를 string, value 를 중복된 개수

성능 개선

• 문제에 제시된 정렬 우선순위과 관계 없이, 
• 입력된 문자열 배열을 단어 순으로 정렬하면, 중복된 단어는 서로 인접해 있다는 것을 이용하도록 한다.

---

[3. 코드]

	#include <iostream>
	#include <algorithm>
	#include <string>
	#include <numeric>
	#include <vector>
	int main()
	{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int N, M;
	std::cin >> N >> M;
	std::vector<std::string> words;
	for (int i=0; i<N; i++) {
	std::string t;
	std::cin >> t;
	if (t.size() < M) continue;
	// 일단 모든 단어를 벡터에 push 한다.
	words.emplace_back(t);
	}
	std::vector<int> index(words.size());
	// 중복된 단어의 개수를 세기 전에
	// 먼저 모든 단어의 개수를 0으로 초기화 한다.
	// 단어 개수가 1개 보다 적은 경우는
	// 중복된 단어이므로 출력하지 않도록 한다.
	std::vector<int> counts(index.size(), 0);
	std::iota(index.begin(), index.end(), 0);
	std::sort(index.begin(), index.end(), [&words](const int l, const int r) {
	// 단어를 오름차순을 정렬한다.
	return words[l] < words[r];
	});
	auto itr0 = index.begin();
	int count = 1;
	for (auto itr1 = std::next(itr0); itr1 != std::end(index); itr1++) {
	if (words[*itr0] == words[*itr1]) {
	// 같은 단어인 경우, 중복된 단어 개수를 증가
	count++;
	}
	else {
	// 다른 단어인 경우,
	// 이전 위치(= 이전 단어) 의 중복된 개수를 저장한다.
	counts[*std::prev(itr1)] = count;
	itr0 = itr1;
	count = 1;
	}
	}
	// **마지막 단어, 개수를 저장한다. (누락되지 않도록 주의)**
	counts[index.back()] = count;
	std::iota(index.begin(), index.end(), 0);
	std::sort(index.begin(), index.end(), [&](const int l, const int r){
	if (counts[l] == counts[r]) {
	if (words[l].size() == words[r].size()) {
	return words[l] < words[r];
	}
	else {
	return words[l].size() > words[r].size();
	}
	}
	else {
	return counts[l] > counts[r];
	}
	});
	for (const int i : index) {
	if (counts[i] == 0) continue; // 개수가 0인 (중복된) 단어는 출력하지 않도록 한다.
	std::cout << words[i] << "\n";
	}
	return 0;
	}

view raw 20920.cpp hosted with ❤ by GitHub