백준 20920 c++ "영단어 암기는 괴로워" -PlusUltraCode-

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

 

[필자 사고]

문자열 관련 자료구조 연습용으로 좋은 문제였다.

정렬 관련 함수 정의할 때 3가지 경우를 신경 써야 되기 때문에 학습에 많은 도움이 되었다.

처음 map에 해당 단어들을 담았고 우선순위 큐를 이용핳여 단어들을 collect했다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

1. 입력 처리 (Input 함수)

• N: 전체 입력될 단어의 수
• M: 유효한 단어로 인정받기 위한 최소 길이
• 작동 방식:
  N개의 단어를 입력받아, 길이가 M 이상인 단어만 저장합니다.
  저장은 map<string, int> 형태로, 각 단어가 몇 번 나왔는지 빈도 수를 저장합니다.

---

2. 우선순위 큐를 활용한 정렬 (Game_Start 함수)

• 유효 단어들을 하나씩 우선순위 큐에 넣습니다.
  이때 각 단어는 Node라는 구조체로 표현되며 다음 정보를 담고 있습니다:
  • 문자열 자체
  • 문자열 길이
  • 등장 횟수
• cmp 구조체를 이용한 사용자 정의 정렬 기준:
  1. 등장 횟수가 높은 순
  2. 단어 길이가 긴 순
  3. 사전 역순 (사전 순으로 뒤에 있는 단어가 우선)

---

3. 출력

• 우선순위 큐에서 하나씩 꺼내며, 위 기준에 따라 정렬된 단어들을 순서대로 출력합니다.

---

정리

이 프로그램은 다음 조건에 따라 단어를 정렬하고 출력합니다:

1. 길이가 M 이상인 단어만 고려
2. 자주 등장한 단어일수록 우선
3. 등장 횟수가 같다면 더 긴 단어가 우선
4. 길이도 같다면 사전에서 뒤에 있는 단어가 우선

[소스 코드]

#include <iostream>
#include <map>
#include <cstring>
#include <queue>
using namespace std;

typedef struct Node {
	string str;
	int size;
	int count;
}Node;

struct cmp {
	bool operator()(const Node& a, const Node& b) const {
		if (a.count == b.count && a.size == b.size) {
			return a.str > b.str;
		}
		if (a.count == b.count) {
			return a.size < b.size;
		}
		return a.count < b.count; 
	}
};


int N, M;
map<string, int> myMap;
priority_queue<Node, vector<Node>, cmp> pq;


void Input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		if (str.size() >= M) {
			myMap[str] += 1;
		}
	}
}

void Game_Start() {
	for ( auto& pair : myMap) {
		Node node = { pair.first,pair.first.size(),pair.second };
		pq.push(node);
	}

	while (!pq.empty()) {
		cout << pq.top().str << '\n';
		pq.pop();
	}
}

int main(void) {
	Input();
	Game_Start();
}