1. 1st Source ¶
#include <map>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
class Anagram
{
private:
typedef map< string, map<char, int> >::iterator MSMCII;
typedef map< char, int > MCI;
map< string, map<char, int> > _anagramTable;
public:
void CalWhatAnagram(const string& str)
{
MCI howManyEachAlphabet;
for(int i = 0 ; i < str.size() ; ++i)
howManyEachAlphabet[ str[i] ] += 1;
_anagramTable[str] = howManyEachAlphabet;
}
void Show()
{
while( !_anagramTable.empty() )
{
MCI value = _anagramTable.begin()->second;
for(MSMCII i = _anagramTable.begin() ; i != _anagramTable.end() ; )
{
if(i->second == value)
{
cout << i->first << " ";
_anagramTable.erase(i++);
}
else
{
++i;
}
}
cout << endl;
}
}
};
int main()
{
Anagram anagram;
ifstream fin("input.dat");
string t;
while(!fin.eof())
{
getline(fin, t);
anagram.CalWhatAnagram(t);
}
anagram.Show();
fin.close();
return 0;
}
2. 1st ë¶„ì„� ¶
- ë¨¼ì € ì‚¬ì „ 파ì�¼ì�„ ìž…ë ¥ë°›ìœ¼ë©´ì„œ, 키값ì�€ ê·¸ 단어, 키ì—� 해당하는 ê°’ì�€ <알파벳, ê·¸ 알파벳ì�˜ 출현 개수> Pairì�¸ Pair를 ìƒ�성한다.(--; ë”ê°€ 좀 ë§�ì�´ ì�´ìƒ�하군)
- 여기서, 단어ì�˜ 갯수를 nê°œ, 단어ì�˜ í�‰ê· 길ì�´ë¥¼ mì�´ë�¼ 하면, ì�´ê²ƒì�´ ì–´ë–¤ Pairì�¸ê°€ íŒ�단하는ë�° Θ(mn)ì�˜ 시간ì�´ 걸린다. 다시 그것ì�„ map 컨테ì�´ë„ˆì—� 집어넣는ë�° Θ(n)ì�˜ 시간ì�´ 걸린다.
- 여기서, 단어ì�˜ 갯수를 nê°œ, 단어ì�˜ í�‰ê· 길ì�´ë¥¼ mì�´ë�¼ 하면, ì�´ê²ƒì�´ ì–´ë–¤ Pairì�¸ê°€ íŒ�단하는ë�° Θ(mn)ì�˜ 시간ì�´ 걸린다. 다시 그것ì�„ map 컨테ì�´ë„ˆì—� 집어넣는ë�° Θ(n)ì�˜ 시간ì�´ 걸린다.
- ì¶œë ¥í• ë•ŒëŠ” map ê°�체를 순회하면서, 한번 첨부터 ë��까지 ë�Œë©´ì„œ anagramì°¾ì�€ê±´ 지워준다.(좀 안좋ì�€ 방법 같기는 하다.)
- �건 최대로 재수 없어�. Θ(n*n) ��� 시간� 걸리지는 않는다.
- �건 최대로 재수 없어�. Θ(n*n) ��� 시간� 걸리지는 않는다.
- ì�¼ë°˜ì �으로 단어ì�˜ 갯수는 단어ì�˜ 길ì�´ë³´ë‹¤ëŠ”... 아무래ë�„ í�´ê²ƒì�´ë‹¤. ì�´ ì•Œê³ ë¦¬ì¦˜ì�€ ì´� Θ(n*n)ì�˜ 수행시간ì�´ ê±¸ë¦°ë‹¤ê³ í• ìˆ˜ 있다.
3. 1st ê°œì„ ì � ¶
- ë”ê°€ ë�” 좋ì�€ 방법 찾는중.
- 2만개짜리 단어장 구해서 파ì�¼ ì�½ëŠ” ë°©ì‹�으로 바꿨다. 시간 재ë´�ì•¼ê² ë‹¤
- ê¸°ì ˆí•˜ê² ë„¤
; 3ë¶„ 걸리네; ì €ê²Œ 10배로 불어나면..; 대충 5시간으로 불어난다는 것ì�¸ê°€..;
4. 2nd Source ¶
~cpp
#include <map>
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
using namespace std;
class Anagram
{
private:
typedef map<char, int> MCI;
typedef vector<string> LS;
typedef map< MCI, LS > MALS;
typedef MALS::iterator MALSI;
typedef LS::iterator LSI;
MALS _anagramTable;
MCI CalculateWhatAnagram(const string& str)
{
MCI howManyEachAlphabet;
for(int i = 0 ; i < str.size() ; ++i)
howManyEachAlphabet[ str[i] ] += 1;
return howManyEachAlphabet;
}
public:
void BoundAnagram(char* fileName)
{
ifstream fin(fileName);
string str;
while(!fin.eof())
{
getline(fin, str);
_anagramTable[ CalculateWhatAnagram(str) ].push_back(str);
}
}
void ShowAnagram()
{
for(MALSI i = _anagramTable.begin() ; i != _anagramTable.end() ; ++i)
{
for(LSI j = (i->second).begin() ; j != (i->second).end(); ++j)
{
cout << *j << " ";
}
cout << endl;
}
}
};
int main()
{
Anagram ana;
ana.BoundAnagram("input.dat");
ana.ShowAnagram();
return 0;
}
5. 2nd ë¶„ì„� ¶
- ë¨¼ì € ìž…ë ¥ë°›ì�„때ì—�는 key : ì–´ë–¤ 알파벳ì�´ 몇번 나왔나 ì €ìž¥í•œ map 컨테ì�´ë„ˆ, value : ê·¸ string들ì�˜ list. ì�´ëŸ°ì‹�으로 ì €ìž¥í•´ì¤€ë‹¤.
- 1st ë²„ì ¼ì�€ ì¶œë ¥ë¶€ë¶„ì—�서 대부분ì�˜ 시간ì�„ 까먹었었지만.. ì�´ë²ˆì—” ìž…ë ¥ë¶€ë¶„ì—�서 90프로ì�´ìƒ�ì�„ 까먹는거 같다.
- 수행시간ì�„ 대충 계산해볼때, 단어ì�˜ 개수를 n, 단어ì�˜ í�‰ê· 길ì�´ë¥¼ mì�´ë�¼ 하면, ìž…ë ¥ : Θ(mn), ì¶œë ¥ : Θ(n) ì�´ë¯€ë¡œ ì´� 수행시간ì�€ 그런ë�° mì�€ n보다 í› ~~~~~얼씬 작다. Θ(n)ì�´ ë�˜ëŠ”ê±´ê°€?--; ë”ê°€ 좀 궤변 같다.
6. 2nd ê°œì„ ì � ¶
- ë”ê°€ ë�” 좋ì�€ 방법 찾는중.
- 1ë¶„(2만개짜리)으로 줄었다. ë�” 줄ì�¼ìˆ˜ 있ì�„까. ì €ê²Œ 10배로 불어나면..--; 10ë¶„ì •ë�„ 걸리는 걸까.
- ê·¼ë�° 파ì�¼ì—� ì¶œë ¥í•˜ë‹ˆê¹Œ 10ì´ˆ(2만개짜리)ë§Œì—� ë�œë‹¤. ì œê¸¸--; 파ì�¼ì—�다 í• ê»„
- 화면ì—� ì¶œë ¥í•˜ëŠ”ê²Œ ìƒ�ê°�보다 ë§Žì�´ 걸린다. ìž…ë ¥ë�œê±´ "~~~ inputed!"ë�¼ê³ ì¶œë ¥í•˜ê²Œ í–ˆë�”니 10초가 걸리는ë�°, ì €ê±¸ ì¶œë ¥í•˜ì§€ 않으니 1ì´ˆë�„ 안걸린다.
- list를 vector로 ë°”ê¾¸ê³ ì»´í“¨í„° 켜ìž� 마ìž� ì¸¡ì •í•˜ë‹ˆ 6.2ì´ˆ 걸린다.
7. 지금까지 ëŠ�ë‚€ì � ¶
- ì•Œê³ ë¦¬ì¦˜ ê°œì„ ìœ¼ë¡œ ì�´ì •ë�„까지 시간ì�´ 줄어들다니.. ì •ë§� 놀ëž�다. ë�” 줄여ë´�ì•¼ê² ë‹¤.
- �료구조� 잘 골�야 한다.
- 컴터 �태� 좋아야 한다.--;










