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

문제

입출력

풀이

어제 풀었던 최빈값 문제와 비슷한 느낌이라
자료구조로 vector와 map을 떠올렸다.
처음에는 map에 냅다 입력받으면서 정렬까지 하려고 했는데
커스텀 정렬 함수 생긴 게 마음에 안들어서 vector로 틀었다.

vector에 입력을 받으면서 M보다 짧은 단어를 1차로 걸러준다.
vector를 돌며 map에 빈도수를 계산해주고,
문제의 조건에 따라 1. 빈도 2. 길이 3. 사전순으로 정렬하는 cmp 함수와 함께 vector 정렬 과정을 거치게 된다.

정렬된 vector에서 중복값을 제거해주고,
크기만큼 돌며 출력하면 문제 해결 ~

vector 중복 제거 복습

#include <algorithm>
#include <vector>

int main() {
	vector<int> v; // <- 값이 들어있다고 가정하자
	v.erase(unique(v.begin(), v.end()), v.end());
    
	return 0;
}

vector 정렬 함수 뜯어보기

bool cmp(string a, string b) {
	if (m[a] != m[b]) return m[a] > m[b];

먼저 비교할 두 string을 인자로 넘긴다.
빈도값이 다르면, 빈돗수가 더 큰 string이 먼저 나오도록 해줬다.

	if (a.length() != b.length()) return a.length() > b.length();
	return a < b;
}

이번엔 길이가 다르면 더 긴 string이 먼저 나오도록 하고,
두 조건문에서 걸러지지 않은 단어는 사전순으로 return한다.
부등호가 항상 헷갈리는데 사전순 빼곤 먼저 나와야 할 것이 더 크다.

코드

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

map<string, int> m;

bool cmp(string a, string b) {
	if (m[a] != m[b]) return m[a] > m[b];
	if (a.length() != b.length()) return a.length() > b.length();
	return a < b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	string word;

	cin >> N >> M;
	vector<string> v;
	
	for (int i = 0; i < N; i++) {
		cin >> word;
		if (word.length() < M) continue;
		v.push_back(word);
	}

	for (int i = 0; i < v.size(); i++) {
		m[v[i]]++;
	}
	sort(v.begin(), v.end(), cmp);
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << "\n";
	}

	return 0;
}

채점