<문제 소개>
<소스 코드>
#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
map<string, int> freq; // 단어별 빈도수(단어, 빈도수)
int maxFreq = 0; // 최대 빈도수
for (int i = 0; i < N; i++)
{
string word;
cin >> word;
// 길이가 M보다 작으면 외우지 않음
if (word.length() < M) continue;
freq[word]++; // 단어별 빈도수 체크
maxFreq = max(maxFreq, freq[word]); // 최대 빈도수 체크
}
// 최대 빈도수만큼의 벡터 생성
vector<vector<string>> wordFreq(maxFreq + 1);
for (auto iter = freq.begin(); iter != freq.end(); iter++)
{
// 빈도수 별로 단어들을 정렬
wordFreq[iter->second].push_back(iter->first);
}
// 빈도수가 큰 단어부터 반복해야 하므로 뒤부터 반복을 진행
for (int i = wordFreq.size() - 1; i > 0; i--)
{
// 최대 길이인 10만큼의 길이별로 정렬할 단어장 생성
vector<set<string>> wordList(11);
// 같은 빈도수를 가진 단어들끼리 비교
for (int j = 0; j < wordFreq[i].size(); j++)
{
string curWord = wordFreq[i][j]; // 현재 단어
int curWordLength = curWord.length(); // 현재 단어의 길이
// 길이별로 단어를 정렬
wordList[curWordLength].insert(curWord);
}
// 이제까지 입력된 단어들을 출력
// 길이가 긴 단어부터 출력해야 하므로 뒤부터 반복
for (int i = wordList.size() - 1; i > 0; i--)
{
// 알파벳 사전 순으로 출력해야 하므로 앞부터 차례로 출력
for (auto jiter = wordList[i].begin(); jiter != wordList[i].end(); jiter++)
{
cout << *jiter << "\n";
}
}
}
return 0;
}<소스코드 2> - sort 이용
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
// 길이별로 정렬되게하는 함수 -> a가 b보다 더 우선순위가 높은지 리턴
bool LengthSort(pair<int, string> a, pair<int, string> b)
{
if (a.first == b.first)
{
// 빈도가 같은 경우
if (a.second.length() == b.second.length())
{
// 단어의 길이가 같은 경우 -> 알파벳 순으로 정렬
return a.second < b.second;
}
else
{
// 단어의 길이가 같은 경우 -> 길이가 긴 순으로 정렬
return a.second.length() > b.second.length();
}
}
else
{
// 빈도가 다른 경우 -> 빈도순으로 정렬
return a.first > b.first;
}
}
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N, M;
cin >> N >> M;
map<string, int> freqCheck; // 빈도수 체크용
for (int i = 0; i < N; i++)
{
string s;
cin >> s;
// 길이가 M보다 작은 경우 넘어감
if (s.length() < M) continue;
freqCheck[s]++; // 빈도수 체크
}
vector<pair<int, string>> wordList; // 단어장(빈도수, 단어)
for (auto iter = freqCheck.begin(); iter != freqCheck.end(); iter++)
{
// 빈도수와 단어들을 나열하여 저장
wordList.push_back({ iter->second, iter->first });
}
// 사용자 정의 정렬
sort(wordList.begin(), wordList.end(), LengthSort);
// 출력
for (auto iter = wordList.begin(); iter != wordList.end(); iter++)
{
cout << iter->second << "\n";
}
return 0;
}<풀이과정>
1. N과 M을 입력받고, 단어별 빈도수를 저장할 변수를 맵 freq와, 최대 빈도수를 나타낼 변수 maxFreq를 선언한다.
2. N만큼 반복하며 길이가 M보다 작은 단어들을 제외하고 나머지 단어들의 빈도수와 최대 빈도수를 체크하며 반복을 진행한다.
3. 위의 과정을 진행하면 각 단어가 알파벳 순으로 빈도수가 구해진 상태가 된다.
4. 이제 빈도수로 단어들을 정렬하기 위해 이중벡터 wordFreq를 maxFreq+1의 크기로 선언하여 인덱스를 빈도수로 사용할 것이다.
5. 앞서 저장한 맵 freq를 차례로 돌면서 freq의 value에 해당되는 값을 인덱스로 가지는 wordFreq에 freq의 key에 해당되는 단어를 넣어주게 되면 빈도수 별로 단어들이 들어가게 되어 정렬된 상태가 된다.
6. 즉, 이번 반복을 통해 빈도수로 정렬된 이중 벡터를 구할 수 있었다.
7. 이제 길이순으로 정렬을 할건데 빈도수가 큰 것이 우선순위이므로 각 빈도수 별로 정렬을 진행할 것이다.
8. wordFreq의 뒤부터 반복하여 빈도수가 큰 인덱스부터 접근하고, 매 반복마다 길이별로 정렬하면서 동시에 알파벳 순으로도 정렬하기 위해 set 컨테이너를 사용했다.
9. 따라서 wordList는 각 원소를 string형 set로하고, 단어의 최대 길이인 10까지 인덱스를 가지는 벡터로 초기화하여 선언한다.
10. 다시 wordFreq의 각 원소인 벡터를 돌며 같은 빈도수를 가진 단어들에 접근하고, 각 단어별 길이 curWordLength를 구해 wordList의 curWordLength번째 인덱스에 현재 단어 curWord를 넣어준다.
11. 이 반복이 끝나면 같은 빈도수를 가진 단어들이 길이순으로 wordList에 차례로 들어가 있고, 그 중 같은 길이를 가지는 원소들은 set의 특성으로 인해 알파벳 순으로 정렬되게 된다.
12. 따라서 wordList에 입력된 단어들을 길이가 긴 단어부터 출력해야하므로 역순으로 접근하고, 내부의 set는 순차적으로 접근하는 반복을 진행하며 원소들을 출력해준다.
13. 이렇게 한 반복이 끝나면 가장 큰 빈도수를 가진 단어들이 길이순, 알파벳순으로 정렬되어 출력되고, 다음 반복시에는 wordList가 초기화되어 그 다음으로 큰 빈도수를 가지는 단어들아 같은 방식으로 길이순, 알파벳순으로 정렬되어 출력되는 과정이 진행된다.
14. 따라서 위의 반복을 순차적으로 끝까지 진행하게 되면 모든 단어들이 빈도가 높은순, 길이가 긴순, 알파벳순으로 차례로 정렬되게 된다.
<코멘트>
이번 문제는 내 기준 꽤 어려웠고 푸는데 시간도 오래걸렸다.
어떤 자료구조를 써서 어떻게 정렬을 해야할지 생각해내는 과정이 오래걸렸고, 시간초과까지 생각해서 문제를 풀어야 하는게 까다로운 문제였다.
다른 분들의 풀이를 보았더니 sort의 overloading된 사용자가 정의한 함수를 기준으로 정렬하는 방식을 사용하면 쉽게 풀 수 있는것 같아서 해당 방식으로도 다시 한번 풀어보았다!
사용자 정의 정렬을 따로 좀 더 공부해서 잘 사용할 수 있게 해야겠다..!
<제출결과>
