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

문제

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

풀이

문자열, 정렬, 해시를 사용한 집합과 맵

 

입력받은 문자열을 저장하고 정렬하는 방법이 필요한 문제

• 문자열이 입력된 횟수를 알아야 하므로 map을 사용해야 한다. 
• 입력되는 수가 많지 않기 때문에 unordered_map을 사용한다. 
• 문제에 맞게 정렬이 필요하므로 compare 함수를 생성해야 한다. 
• compare 함수에는 문자열이 입력된 수, 문자열의 길이, 문자열의 사전 순서를 알아야 한다. 

추가로, vector<pair<string, int>>로 unordered_map의 begin(), end()를 생성자의 인자로 활용하여 vector를 생성할 수 있다. 이렇게 만든 vector를 compare함수로 정렬시켜 문자열을 출력한다. 

코드

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<string, int> word_count;

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

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

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; ++i)
    {
        string word;
        cin >> word;

        if (word.length() >= M)
        {
            word_count[word]++;
        }
    }

    // map의 iterator는 pair로 이루어진다. 
    // 동일한 pair로 구성된 vector를 다음의 생성자로 만들 수 있다.
    vector<pair<string, int>> words(word_count.begin(), word_count.end());

    sort(words.begin(), words.end(), compare);

    for (pair<string, int>& word : words)
    {
        cout << word.first << '\n';
    }

    return 0;
}