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

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

 

언어: C++, 시간: 160ms

 

💡문제 아이디어

Hash와 PQ에서의 구조체 정렬을 연습하기 좋은 문제.

Hash를 이용해 시간복잡도를 O(1)로 빈도수를 저장하고, 

PQ와 구조체를 이용해 문제의 조건으로 정렬한다.

 

💡문제 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;


// pq에 사용할 구조체
struct word{
	int wordFreq;
	int wordLen;
	string wordName;
};

// pq용 정렬 구조체 - 1. 빈도 내림차순, 2. 길이 내림차순, 3.ASCHII오름차순
struct compare {
	bool operator()(const word a, const word b) {
		if (a.wordFreq == b.wordFreq) {
			if (a.wordLen == b.wordLen) {
				return a.wordName > b.wordName;
			}
			else return a.wordLen < b.wordLen;
		}
		else return a.wordFreq < b.wordFreq;
	}
};

int N, M;
string inputWord;
unordered_map <string, word> wordInfo;						// 단어 저장용 컨테이너
priority_queue <word, vector<word>, compare> wordList;		// 정렬용 단어사전


int main() {
	//freopen("sample_input.txt", "r", stdin);

	cin >> N >> M;
	for (int i = 0; i < N; i++){
		cin >> inputWord;
		int wordLen = inputWord.length();
		if (wordLen < M) continue;

		// hash에 빈도수 저장 
		if (wordInfo.count(inputWord) == 0) {
			wordInfo[inputWord] = { 1, wordLen, inputWord };
		}
		else {
			wordInfo[inputWord].wordFreq += 1;
		}
	}

	// hash 순회하며 단어사전에 저장 
	for (auto it = wordInfo.begin(); it != wordInfo.end(); it++){
		word curWord = { it->second.wordFreq, it->second.wordLen, it->second.wordName };
		wordList.push(curWord);
	}

	// 단어사전 단어 출력
	while (!wordList.empty()) {
		word outputWord = wordList.top();
		cout << outputWord.wordName << "\n";
		wordList.pop();
	}

	return 0;
}