[Baekjoon] 20920번: 영단어 암기는 괴로워

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

20920번: 영단어 암기는 괴로워

 

---

 

문제 해결 과정

착안

문자열을 키로 가지며, 등장하는 빈도 수를 값으로 저장하여 문제를 해결하고자 std::map<>과 같은 컨테이너를 활용하고자 하였다. 이때 키의 자료형이 문자열 형이므로 해시 테이블(hash table)을 사용하는 것이 일반적으로 속도 측면에서 유리하기 때문에 std::unordered_map<> 클래스를 사용해 데이터를 입력받아 저장한 다음 std::vector<> 클래스를 활용해 정렬하여 결과를 출력하고자 하였다.

 

구현

문제에서 주어진 정렬 우선순위 대로 람다 표현식(lambda expression)을 이용해 정렬함으로써 문제를 해결하였다.

* 참고) 처음 문제를 해결하면서 std::vector<>로 데이터를 옮길 때 반복문을 통해 옮겼는데, 이 과정이 시간적으로 비효율적임을 확인하여 std::vector<> 클래스의 오버로딩 된 생성자를 사용해 데이터를 옮긴 다음 정렬하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

unordered_map<string, int> Words;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, M = 0;
	cin >> N >> M;

	while (N--)
	{
		string str;
		cin >> str;

		if ((int)str.size() < M)
			continue;

		Words[str]++;
	}

	vector<pair<string, int>> Sorted(Words.begin(), Words.end());
	sort(Sorted.begin(), Sorted.end(),
	     [&](const pair<string, int>& pair1, const pair<string, int>& pair2)
	     {
		     if (pair1.second == pair2.second)
		     {
			     if (pair1.first.size() == pair2.first.size())
				     return pair1.first < pair2.first;

			     return pair1.first.size() > pair2.first.size();
		     }
		     return pair1.second > pair2.second;
	     });

	for (const pair<string, int>& pair : Sorted)
		cout << pair.first << "\n";

	return 0;
}

 

실행 결과