概要
この記事には、POH6+に関するネタバレが含まれます。カンニングしたくない場合は、前々回の記事を読んで勉強するんだ！
……今回はコードを改良する話。
2015/09/04：重大なミスが見つかりましたので修正しました。
STLが足りてない！
実は前回挙げたコードには問題がある。100点満点ではあるのだが、美しくない。つまり、STLの力を生かしきれてないということ。
手順としては、いかに「左側」一覧と「中央」を抽出するかなのだが、前回でも述べたように文字列は別に重複して構わない。その一方で、前回はゴリゴリと線形検索して、その後にソートを掛けていた。
つまりこれは、std:mapを使うべきところなのではないか？
std::mapなら突っ込んだデータが確実にソートされているので後からソートする必要はないし、同じ単語が複数あればfindで判別してインクリメントすればいい。検索も二分検索(std::unordered_mapならハッシュ法)を使うから超速いし、なにより(std::vectorと同じく)メモリ解放する手間が掛からない。
と言うことで、単語リスト読み込みにはstd::unordered_map、『leftの集合』を入れるのにはstd::mapを使用した。以下ソース。
投稿しなおしたコード(修正前)
code5.cpp
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
using namespace std;
int main(void){
// 単語リストに単語を代入する
int N;
cin >> N;
unordered_map<string, int> word; //単語リスト(単語->回数)
for(int i = 0; i < N; ++i){
string temp;
cin >> temp;
// 単語リスト
if (word.find(temp) != word.end()){
++word.at(temp);
}else{
word[temp] = 1;
}
}
// 単語リストから「左側」一覧と「中央」を取得する
map<string, int> left; //「左側」のリスト
string center_word; int center_count = 0; //「中央」
for(auto it : word){
// 単語を反転したものを用意する
string reverse_word = it.first;
reverse(reverse_word.begin(), reverse_word.end());
// 「中央」ならば、「より数が多い」か「数は同じでより若い」もののみ受け入れる
if(it.first == reverse_word){
if(center_count < it.second){
center_word = reverse_word;
center_count = it.second;
}else if(center_count == it.second){
if(center_word > reverse_word){
center_word = reverse_word;
}
}
}else{
// 「左側」ならば、「より若い」もののみ受け入れ、値は「より数が少ない」方にする
if(word.find(reverse_word) != word.end()){
left[min(it.first, reverse_word)] = min(it.second, word.at(reverse_word));
}
}
}
// 解を出力する
// (左側→中央→右側。右側は左側の反転、中央は当該文字列をただ吐くだけ)
string all_left_word = "";
for(auto it : left){
for(int i = 0; i < it.second; ++i){
all_left_word += it.first;
}
}
cout << all_left_word;
for(int i = 0; i < center_count; ++i){
cout << center_word;
}
reverse(all_left_word.begin(), all_left_word.end());
cout << all_left_word << endl;
}
ちなみにコイツを魔圧縮したら635バイトになった。まあまあ縮んだんじゃないかな？
投稿しなおしたコード(修正後)
code5_2.cpp
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
using namespace std;
int main(void){
// 単語リストに単語を代入する
int N;
cin >> N;
unordered_map<string, int> word; //単語リスト(単語->回数)
for(int i = 0; i < N; ++i){
string temp;
cin >> temp;
// 単語リスト
if (word.find(temp) != word.end()){
++word.at(temp);
}else{
word[temp] = 1;
}
}
// 単語リストから「左側」一覧と「中央」一覧を取得する
map<string, int> left; //「左側」のリスト
map<string, int> center; //「中央」のリスト
for(auto it : word){
// 単語を反転したものを用意する
string reverse_word = it.first;
reverse(reverse_word.begin(), reverse_word.end());
// 「中央」ならば、とりあえず全て取得する
if(it.first == reverse_word){
center[reverse_word] = it.second;
}else{
// 「左側」ならば、「より若い」もののみ受け入れ、値は「より数が少ない」方にする
if(word.find(reverse_word) != word.end()){
left[min(it.first, reverse_word)] = min(it.second, word.at(reverse_word));
}
}
}
// 「中央」のうち、2個以上ある単語はそのうちの半分を左側、もう半分を右側に振り分けておく
// 例えば7個あった場合は3個を左側に入れて残り1個、8個なら4個入れて残り0個
for(auto &it : center){
if(it.second >= 2){
left[it.first] = it.second / 2;
it.second = it.second % 2;
}
}
// 解を出力する
// (左側→中央→右側。右側は左側の反転、中央は左右に過剰分を振り分けた後最若を出力)
string all_left_word = "";
for(auto &it : left){
for(int i = 0; i < it.second; ++i){
all_left_word += it.first;
}
}
cout << all_left_word;
for(auto &it : center){
if(it.second == 1){
cout << it.first;
break;
}
}
reverse(all_left_word.begin(), all_left_word.end());
cout << all_left_word << endl;
}