문제 출처

1. 문제설명

  • 단어장을 만드는 규칙은 다음과 같다.
    • 자주 나오는 단어일수록 앞에 배치한다.
    • 해당 단어의 길이가 길수록 앞에 배치한다.
    • 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.
    • M보다 크거나 같은 단어들만 외운다.



2. 알고리즘 설계

  • 대놓고 map을 써야하는 문제이다.
    • 맵을 안 쓴다면… 풀이가 가능한가..?
  • key 값은 입력된 단어, value는 개수로 저장하면 된다.



3. 로직

  • 문자열을 입력받고,
  • 해당 키 값에 size 즉, 길이가 M보다 크면 개수 카운팅
    • M보다 작은 문자열은 어차피 필요가 없다.
  • 맵을 벡터에 복사해준다.
    • 정렬을 위해서!
    • 매우 간단히 가능하다. vector<psi> tmp(um.begin(), um.end());
  • 정렬 기준
    • 사전 순서라면, str1<str2 하면 된다.
    • 길이 순이라면, str1.size()<str2.size() 하면 된다.



4. 전체 코드

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
using psi = pair<string, int>;

bool compare(const psi &a, const psi &b) {
	if (a.second == b.second) {
		if (a.first.size() == b.first.size()) return a.first < b.first;
		return a.first.size() > b.first.size();
	}
	return a.second > b.second;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	unordered_map<string, int> um;
	vector<string> v;
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string tmp; cin >> tmp;
		if (tmp.size() >= m) um[tmp]++;
	}
	
	vector<psi> tmp(um.begin(), um.end());
	sort(tmp.begin(), tmp.end(), compare);

	for (psi a : tmp) cout << a.first << '\n';
	return 0;
}