들숨날숨

[C/C++]백준 20920

 
  • Mar 23, 2021

백준 20920 - 영단어 암기는 어려워 (실버3)

20920 문제 링크

화은이를 위한 영단어장을 다음 조건에 따라 만들자
1. 특정 길이 이하인 단어는 적지 않는다.
2. 자주 나오는 단어일 수록 앞에 배치한다.
3. 해당 단어가 길수록 앞에 배치한다.
4. 알파벳 사전 순으로 앞에 있을수록 앞에 배치한다.
단어 길아나 사전순으로 정렬하는 것은 sort를 이용하고, 단어의 빈도수를 저장하기 위해 map을 이용했다.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector <string> voca; //희은이의 단어장
map<string, int> mp; //단어의 빈도수를 저장
string v;
다음과 같이 선언했고, main함수를 보자
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    //시간을 단축하기 위해 작성
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> v;
        if (v.size() < m) continue; //길이가 m이하면 다음 단어를 입력받는다.
        if (mp.find(v)==mp.end()) { //입력받은 단어가 단어장에 없는 단어일 경우
            mp[v] = 0;
            voca.push_back(v);
        }
        mp[v]++; //입력받은 단어가 단어장에 있을 경우 나온 횟수를 +1해준다.
    }
    sort(voca.begin(), voca.end(), compare); //compare조건에 따라 정렬

    for (int i = 0; i < voca.size(); i++) { //최종 출력
        cout << voca[i] << '\n';
    }
}
시간제한이 1초로 짧은 편이므로 cin.tie(nullptr); ios::sync_with_stdio(false);를 적어줘야 한다.
다음으로 정렬 조건을 살펴보자
bool compare(string a, 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];
}
이렇게 코드를 완성하였고, 최종 코드는 다음과 같다.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
using namespace std;
int n, m;
vector <string> voca;
map<string, int> mp;
string v;
bool compare(string a, 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];
}

int main() {
    
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> v;
        if (v.size() < m) continue;
        if (mp.find(v)==mp.end()) {
            mp[v] = 0;
            voca.push_back(v);
        }
        mp[v]++;
    }
    sort(voca.begin(), voca.end(), compare);

    for (int i = 0; i < voca.size(); i++) {
        cout << voca[i] << '\n';
    }
}
Search