20920 - 영단어 암기는 괴로워

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

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

생각해 보기

• 정렬 순서는 다음과 같다.
  • 나오는 빈도
  • 길이가 긴 순서
  • 사전 앞 순서
• string 비교를 할때 작은걸 구하기 위해선 compare도 가능하지만 string a < string b 도 가능하다.
• compare == -1을 사용하면 작동이 확실하지 않은 듯 하다.
• 입력을 받을 때 길이가 M아래인 경우 스킵하자.
• 정렬을 할 때 map을 들어가서 빈도 값을 가져오는 경우 map도 logn의 시간 복잡도를 가지게 되어 손해를 보게 된다.

코드

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

int N,M;
string tmp;
map<string, int> vocalist;

void input(){
    cin>>N>>M;
    while(N--){
        cin>>tmp;
        
        if(tmp.length() < M)
            continue;

        if(vocalist.find(tmp) == vocalist.end()){
            vocalist[tmp]=1;
        }
        else{
            ++vocalist[tmp];
        }
    }
}

bool cussort(pair<string, int> &a, pair<string, int> &b){
    if(a.second == b.second){
        if(a.first.length()==b.first.length())
            return a.first < b.first;
        return a.first.length() > b.first.length();
    }
    return a.second > b.second;
}

void solution(){
    vector<pair<string, int> > ans (vocalist.begin(), vocalist.end());
    sort(ans.begin(),ans.end(),cussort);
    for(int i=0,len=ans.size();i<len;++i){
        cout<<ans[i].first<<'\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}