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

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

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

드디어 찾았다!!!!

항상 시험에서 마주할 때마다 어렵지는 않은데, 시간을 많이 잡아먹어서 곤란했던 문제이다.

단순한 정렬이 아니라, 여러 조건들에 맞춰서 정렬을 하는 점이 까다롭다.

 

드디어 스스로 풀긴 풀었는데, 지나치게 코드가 복잡했다.

특히 처음에 입력할 때는 string이 키값이었다가, 나중에 문제를 풀때는 정렬을 위해 빈도가 키값으로 와야한다는 점이 어려웠다.

 

 

처음에 나는 일종의 사전같이 한 단어에 대한 번호를 unique하게 붙여서, 다른 map에는 반대로 인덱스를 통해 바로바로 단어를 파악할 수 있도록 2개의 unordered_map을 썼다.

그리고 해당 단어에 대한 번호를 가지고 벡터에 빈도와 단어의 길이를 입력해 정렬을 하였다.

그런데 가만 보면 지나치게 중복되는 데이터가 많다는 생각이 들고, 자료구조를 너무 많이 써서 풀다가 헷갈리는 지경에 이른다. 🤯

 

무엇보다 unordered_map과 struct의 사용 방법도 어려웠다. struct에 대한 vector에 push_back할 때 bracket이 잘 안돼서 곤란했는데, 알고보니 C++17 버전 이전에는 bracket으로 삽입하는 것이 불가능했다.

 

대신 이렇게 가능하기 때문에, 만약 C++17 이전 버전에서는 아래와 같이 처리하면 된다.

Word w;
w.frq = 1;
w.num = num;
w.len = word.length();
sorting.push_back(w);

전체적인 코드는 아래와 같다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
struct Word {
	int frq, len, num;
};
unordered_map<string, int> dictionary;
unordered_map<int,string> dictionary2;
// 빈도, 길이, 번호
vector<Word> sorting;

bool cmp(Word &a, Word &b) {
	if(a.frq == b.frq) {
		if(a.len == b.len) {
			return dictionary2[a.num] < dictionary2[b.num];
		}
		return a.len > b.len;
	}
	return a.frq > b.frq;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for(int i = 0;i < n;i++) {
		string word;
		cin >> word;
		if(word.length() >= m) {
			if(dictionary.find(word) != dictionary.end()) {
				int num = dictionary[word];
				sorting[num].frq++;
			}
			else {
				int num = dictionary.size();
				dictionary[word] = num;
				dictionary2[num] = word;
				sorting.push_back({1, (int) word.length(), num});
			}
		}
	}


	sort(sorting.begin(), sorting.end(), cmp);

	for(int i = 0;i < sorting.size();i++) {
		cout << dictionary2[sorting[i].num] << '\n';
	}

}

 

여기서 더 나아가 unordered_map 형식의 자료구조를 하나만 쓰고, 굳이 단어를 번호화하지 않는다.

정렬 기준을 다시 한 번 살펴보면, 빈도, 길이, 알파벳 순인데, 길이와 알파벳 순은 단어를 통해 바로 파악할 수 있기 때문이다.

그래서 string을 키로 빈도를 value로 삽입을 한 뒤, 나중에 순회하면서 정렬기준을 정리하면 깔끔하다.

 

여기서 더욱이 unordered_map을 쓸 때, key가 없는 경우 [] operator를 쓰면 자동으로 value가 0으로 초기화된다.

그렇기 때문에 초기 삽입 여부를 구분하지 않고 후위 증가 연산자를 써서 간단하게 코드를 작성할 수 있다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
unordered_map<string, int> checklist;

bool cmp(pair<int,string> &a, pair<int,string> &b) {
	if(a.first == b.first) {
		if(a.second.length() == b.second.length()) {
			return a.second < b.second;
		}
		return a.second.length() > b.second.length();
	}
	return a.first > b.first;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	while(n--) {
		string str;
		cin >> str;
		if(str.length() < m) continue;
		checklist[str]++;
	}
	// 빈도, 해당 문자
	vector<pair<int,string>> wordbook;

	for(auto w : checklist) {
		wordbook.push_back({w.second, w.first});
	}

	sort(wordbook.begin(), wordbook.end(), cmp);

	for(auto w: wordbook) {
		cout << w.second << '\n';
	}
}