20920 c++ - 영단어 암기는 괴로워

 

[C++] map / multimap / unordered_map / unordered_multimap

 

map으로 접근해서 vector로 끝냈습니다.

기본적으로 c++의 map은 ordered와 unordered로 나뉩니다. 자동 정렬이 되는 맵이 있고, 해쉬 맵이 있습니다.

자주나오는 단어를 찾기 위해서 상수로 인덱싱이 가능한 unordered_map을 사용해서 카운트를 처리하였고, 정렬을 위해서  ordered한 map 을 고려해보다가가 multimap으로도 풀 수 있을거 같아서. vector로도 풀어보고, multimap으로도 풀어봤습니다.

 

vector 풀이

#include <algorithm>
#include <cstring>
#include <iostream>
#include <unordered_map>
#include <vector>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)

using namespace std;

bool vcmp(string s1, string s2) {
  int s1len = s1.size(), s2len = s2.size();

  if (s1len == s2len) return s1 < s2;
  return s1len > s2len;
}

int main() {
  FASTIO;

  int n, m, count = 0;
  cin >> n >> m;
  string s;
  unordered_map<string, int> c;
  for (int i = 0; i < n; i++) {
    string t;
    cin >> t;
    if (t.size() >= m) {
      c[t]++;
      count = max(count, c[t]);
    }
  }

  while (count--) {
    vector<string> v;
    for (auto cc : c) {
      if (cc.second == count + 1) {
        v.push_back(cc.first);
      }
    }
    sort(v.begin(), v.end(), vcmp);
    for (auto vv : v) {
      s += vv + "\n";
    }
  }

  cout << s;
  return 0;
}

 

multimap 풀이

#include <iostream>
#include <map>
#include <unordered_map>

#define FASTIO ios::sync_with_stdio(0), cin.tie(0)

using namespace std;

struct mcmp {
  bool operator()(const pair<int, string> &a,
                  const pair<int, string> &b) const {
    if (a.first == b.first) {
      int avlen = a.second.size(), bvlen = b.second.size();
      if (avlen == bvlen) {
        return a.second < b.second;
      }
      return avlen > bvlen;
    }
    return a.first > b.first;
  }
};

int main() {
  FASTIO;

  int n, m;
  cin >> n >> m;

  unordered_map<string, int> c;
  for (int i = 0; i < n; i++) {
    string t;
    cin >> t;
    if (t.size() >= m) {
      c[t]++;
    }
  }

  multimap<pair<int, string>, string, mcmp> freq_map;
  for (const auto &pair : c) {
    freq_map.insert({{pair.second, pair.first}, pair.first});
  }

  for (const auto &entry : freq_map) {
    cout << entry.second << "\n";
  }

  return 0;
}