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

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

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

코드

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

map<string, int> word;

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

int main()
{
	ios::sync_with_stdio(false); // 빠른 입출력
	cin.tie(NULL); // 빠른 입출력
	cout.tie(NULL); // 빠른 입출력

	int n, m;
	string s;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s;
		if (s.length() < m) continue;
		else {
			auto item = word.find(s);
			if (item != word.end()) (item->second)++;
			else word.insert({ s, 1 });
		}
	}
	
	vector<pair<string, int>> v(word.begin(), word.end());
	sort(v.begin(), v.end(), cmp);

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

 

코드 설명

입력되는 단어의 수가 많으므로 먼저 빠른 입출력을 위한 코드 세 줄을 main 함수 상단에 적는다. 이후 int형 변수 n, m과 단어를 입력받기 위해 string형 변수 s를 선언한다.  n, m을 입력받은 뒤 반복문으로 단어를 입력받는다.

 

단어, 단어의 등장횟수를 map을 이용해 저장한다. 단어가 입력될 때마다 해당 단어가 존재하는지를 찾아야하는데, map을 이용하면 빠르게 대상이 존재하는지를 알 수 있기 때문에 map을 사용하면 좋을 것 같다고 판단했다. 단어를 입력받고 길이가 m보다 짧다면 읽는 것만으로도 외울 수 있으므로 map에 새로운 단어를 추가하거나 단어의 등장횟수를 업데이트하지 않는다. 길이가 m 이상인 단어에 대해 단어가 map에 존재한다면 등장횟수를 1 증가시키고, 존재하지 않는다면 새로운 단어이므로 단어(s)와 단어의 의 등장횟수(1)를 map에 삽입한다.

 

입력이 종료되면 map에 저장된 내용들을 정렬하기 위해 vector로 변환한다. 그리고 sort함수를 이용해 정렬한다. cmp 함수로 문제에서 언급된 우선순위를 구현해준다. 첫 번째 if문이 1번 우선순위이다. 단어의 등장횟수가 다를 경우 등장횟수가 많은 단어가 앞에 오도록 한다. 두 번째 if문에서는 해당 단어의 길이가 다르다면 긴 단어가 먼저 오도록 한다. if문들에 해당하지 않는 경우에 대해서는 사전 순으로 정렬한다. 정렬이 끝나면 반복문으로 단어들을 출력한다.

 

느낀 점

문제를 보자마자 검색이 많다는 생각에 map을 이용했다. 정렬 조건을 작성하는 것은 어렵지 않았으나 map을 조건에 맞게 정렬하기 위해 어떻게 할지 고민했다. 다른 분의 글을 찾아보고 map을 vector로 변환하면 정렬할 수 있다는 것을 알게 되었다. 해당 방법을 이용해서 코드를 금방 짰고 한 번에 통과했다!

 

 

참고한 글

https://velog.io/@keybomb/cpp-map%EC%9D%84-value-%EA%B8%B0%EC%A4%80%EC%9C%BC%EB%A1%9C-%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0

[cpp] map을 value 기준으로 정렬하기