[백준 C++] 20920. 영단어 암기는 괴로워

문제 링크

---

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

접근 방법

---

1. 단어와 단어의 빈도수를 기록하기 위해 map을 사용합니다.
2. 문제의 조건으로 정렬하기 위해 vector를 사용합니다.

소스 코드

---

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

using namespace std;

bool comp(pair<string, int>& a, pair<string, int>& b)
{
	if (a.second != b.second) // 빈도수를 비교합니다.
		return a.second > b.second;
        
	if (a.first.length() != b.first.length()) // 단어의 길이를 비교합니다.
		return a.first.length() > b.first.length();
        
	return a.first < b.first; //사전순으로 앞에 있는 단어인지 확인합니다.
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    
	unordered_map<string, int> wordMap;
	vector<pair<string, int>> rst;
	pair<unordered_map<string, int>::iterator, bool> p; // map에 단어를 삽입했을 때 반환값을 확인하기 위한 변수입니다.
	string tmp;                                         // 이미 있는 단어를 삽입했을 때, p.second는 false가 됩니다.
	int len, n;

	cin >> n >> len;
	while (n--)
	{
		cin >> tmp;
		if (tmp.length() >= len) // len 이상의 단어만 map에 삽입합니다.
		{
			p = wordMap.emplace(tmp, 1);
			if (!p.second) // map에 해당 단어가 이미 있을 때
				wordMap[tmp]++;
		}
	}

	copy(wordMap.begin(), wordMap.end(),back_inserter(rst)); // map을 vertor로 옮겨줍니다.
	sort(rst.begin(), rst.end(), comp);
    
	for (auto &a : rst)
		cout << a.first << "\n";
	return 0;
}

코드 설명

---

변수

단어와 단어의 빈도수를 저장하기 위해 unordered_map을 사용하였습니다.

unordered_map을 직접적으로 정렬하지 못하기 때문에 정렬을 하기 위해 vector로 옮겨야 합니다.

map은 값을 삽입할 때마다 pair형태의 값을 반환합니다.  반환된 pair의 첫 번째에는 key, value 값이 들어있고, 두 번째에는 map에 삽입할 수 있는지 여부를 반환합니다. 삽입할 수 있으면 true, 이미 존재하는 값이면 false를 반환합니다.

따라서 map에 값이 존재하는지 알기 위해 pair<unordered_map<string, int>::iterator, bool> p 라는 변수를 사용했습니다.

 

코드

len이상의 단어만 map에 삽입합니다. insert를 쓰지 않고 emplace를 사용한 이유는 포인터 형식이 아닌 요소를 추가할 때, 임시 객체의 생성, 복사, 소멸이 일어나지 않아 빠르기 때문입니다.

map에 해당 단어가 들어있으면 빈도수를 1증가 시켜줍니다.

map에 모든 단어를 넣었다면, map의 요소들을 vector로 옮겨줍니다. 

vector를 화은이가 만들고자하는 단어장의 우선순위로 정렬합니다.