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

문제 요약

문자열이 N개가 주어진다. 문자열 중에서 길이 M보다 작은 문자열은 무시한다. 이 문자열들을 아래와 같은 기준으로 정렬해서 출력하시오.

1. 등장 빈도 수가 더 많은 문자열을 앞에 배치한다.
2. 등장 빈도 수가 같다면 길이가 긴 문자열을 앞에 배치한다.
3. 빈도 수도 같고 길이도 같다면 사전 순으로 앞선 문자열을 앞에 배치한다.

N은 최대 10만이고, M은 최대 10이다. 주어지는 문자열들은 길이 10으넘지 않는다.

풀이

문자열을 입력 받으면서 길이가 M 이상인 문자열들만 map을 이용해서 빈도수를 저장하자.

각 문자열들을 한 번씩만 등장하게 벡터에 저장하고 이 벡터를 주어진 조건에 따라서 정렬하면 된다. 정렬 기준은 함수나 람다 함수를 이용하면 편하다.

지금 보니까 944ms로 아슬아슬하다...

#include<bits/stdc++.h>
using namespace std;

map<string, int> mp;
vector<string> v;
int N, M;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i=0;i<N;++i) {
        string s; cin >> s;
        if(s.size() < M) continue;
        if(mp.find(s) == mp.end()) {
            mp[s] = 0;
            v.push_back(s);
        }
        mp[s]++;
    }
    sort(v.begin(), v.end(), [] (const string &a, const string &b) {
        if(a.size() == b.size() && mp[a] == mp[b]) return a<b;
        else if(mp[a] == mp[b]) return a.size() > b.size();
        return mp[a] > mp[b];
    });
    for(string &s:v) cout << s << '\n';
    return 0;
}