[C++] 백준 알고리즘 20920번 영단어 암기는 괴로워

20920번 문제

영단어 암기는 괴로워

괴롭다 정말

 

이 문제는 시간제한이 매우 짧다.

처음에는 pair만을 이용해서 전체를 비교하고 정렬했었는데 시간초과가 떴었다...

 

이를 해결하려면 map을 이용해야한다.

 

map은 트리구조에다가...

자동으로 정렬이 되기 때문에 내가 원하는대로 정렬시키기가 매우 힘들다

다른 사람들은 어떻게 풀었나 찾아본 결과

 

1. map을 전역변수로 선언해서 정렬

2. map 내용을 pair에 복사해서 정렬

 

크게 이렇게 두 가지 방법이 있었다.

나는 2번으로 풀었었다

 

이 방법 저 방법 다 해보느라 시간 참,,, 많이 쓴 문제..

 

20920

#include<iostream>
#include<map>
#include<algorithm> //sort
#include<vector>
#include<utility> //pair

using namespace std;

//문제에 주어진 정렬
bool cmp(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::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    //추가적으로 endl;보단 '\n';이 더 빠르다고 한다.

	map<string, int> dic;
	
	//입력받을 변수 = 정수 n,m && 문자열 word
	string word;
	int n, m, temp = 0;
	cin >> n >> m;

	//map에 단어 횟수와 단어를 담는다.
	while (temp < n) {
		cin >> word;
		if (word.length() >= m) {
			dic[word]++;
		}
		temp++;
	}

	//map은 정렬하기 힘들다
	//vector로 둘러싼 pair에 값을 그대로 복사한다
	vector<pair<string, int>> v;

	//dic 탐색
	for (auto iter : dic)
		v.push_back(make_pair(iter.first, iter.second));

	//정렬
	sort(v.begin(),v.end(),cmp);

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