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

문제링크 : https://www.acmicpc.net/problem/20920

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M;
map<string, int>m;
vector<pair<string, int>>vec;

bool cmp(pair<string, int>p1, pair<string, int>p2)
{
    if(p1.second == p2.second)
    {
        if(p1.first.size()==p2.first.size()) //단어의 길이가 길수록 앞에
        {
            return p1.first < p2.first; //사전순으로 앞에
        }
        else return p1.first.size() > p2.first.size();
    }
    else return p1.second > p2.second; //자주 나오는 단어일수록 앞에
}

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

    cin >> N >> M;
    for(int i=0; i<N; i++) 
    {
        string s;
        cin >> s;
        if(s.size() < M) continue;
        m[s]++; //문자열에 대한 갯수 저장
    }

    for(auto i : m) vec.push_back({i.first, i.second});
    sort(vec.begin(), vec.end(), cmp);
    for(auto i : vec) cout << i.first << "\n";

    return 0;
}

 

정렬 조건이 여러가지이므로, 이에 맞게 정렬용 함수를 만들어주어 적용해야한다.

일단 입력받을 때 map을 이용하여 입력받은 문자열에 대한 갯수를 카운팅해준다.

이후 map에 대한 쌍 (문자열, 해당 문자열 갯수) 을 벡터에 넣어주고, 해당 벡터를 기준으로 정렬하게 된다.

 

1번 조건은 자주 나오는 단어일수록 앞에 배치하는 것이다.

문자열의 갯수를 이를 위해서 카운팅했으며, 갯수가 많을 수록 앞에 오도록 오름차순 정렬을 해준다.

 

2번 조건은 해당 단어의 길이가 길수록 앞에 배치하는 것이다.

1번 조건에서 갯수가 똑같은 경우 2번으로 내려오게 되며, 각 단어의 길이기준으로 또 오름차순 정렬을 해주게 된다.

 

3번 조건은 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치하는 것이다.

1번과 2번 조건이 모두 같으면 최종 3번으로 내려오게 되며, 사전 순 정렬이므로 내림차순 정렬을 해주게 된다.

 

위 1, 2, 3번에 대한 내용을 cmp 함수로 따로 만들어서 구현해주고, 이를 sort 함수 정렬조건에 넣어주어 정렬해준 후에 문자열에 대해서만 출력해주면 된다.