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

1. 개요

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

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

1-1. 설명

이번 영어 시험에서 틀린 문제를 바탕으로 영단어를 암기하려고 한다. 그 과정에서 효율적으로 영단어를 외우기 위해 단어장을 만든다. 단어장의 단어순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다

 - 자주 나오는 단어일수록 앞에 배치

 - 해당 단어 길이가 길수록 앞에 배치

 - 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치

M보다 짧은 길이 단어 경우 읽는 것만으로 외울 수 있기 때문에 M 이상인 단어들만 외운다. 암기를 효율적으로 할 수 있도록 단어장을 만드는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에는 영어 지문에 나오는 단어 개수 N과 외울 단어 길이 기준이 되는 M이 공백으로 구분되어 주어짐

 - N은 1 이상 100,000 이하, M은 1 이상 10 이하

 - 둘째 줄부터 외울 단어를 입력받으며, 이때 알파벳 소문자로 주어지고 단어의 길이는 10 이하

---

2. 구현

2-1. 풀이

단순히 map을 받아 sort 함수를 이용해 compare 함수를 직접 구현하려 했다. 하지만, 이때 컴파일 에러가 자꾸 나 찾아보니 map은 그 자체만으로 이미 정렬되어 나오는 라이브러리이므로, sort가 되지 않는다고 한다. 그래서 map으로 입력받고 vector로 바꾸어 sort를 진행해주었다. 여기서 정렬되지 않는 unordered_map을 사용해서 구현하려 했으나, 이 또한 sort에서 컴파일 에러가 떴다. map이던, unordered_map이던 두 개 다 sort와 같은 함수는 제공하지 않는 듯했다. 

2-2. 코드

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(const pair<string, int>& a, const pair<string, int >& b);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int N, M, index = 0;
    cin >> N >> M;
    map<string, int> words;
    string input;

    for (int i = 0; i < N; i++) {
        cin >> input;
        if (input.size() < M) continue;
        words[input] += 1;
    }

    vector<pair<string, int>> vecWord(words.begin(), words.end());
    sort(vecWord.begin(), vecWord.end(), compare);

    vector<pair<string, int>>::iterator it;
    for (it = vecWord.begin(); it != vecWord.end(); it++) {
        cout << it->first << "\n";
    }

    return 0;
}

bool compare(const pair<string, int>& a, const pair<string, int>& 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;
}