U E D R , A S I H C RSS

Classify By Anagram/�수

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)ì�˜ 시간ì�´ 걸린다.
  • ìœë ¥í• ë•ŒëŠ” map ê°�체를 순회하면서, 한번 첨부터 ë��까지 ë�Œë©´ì„œ anagramì°¾ì�€ê±´ 지워준다.(좀 안좋ì�€ 방법 같기는 하다.)
    • ì�´ê±´ 최대로 재수 없어ë�„. Θ(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. 지금까지 �낀�

  • 알고리즘 개선으로 ì�´ì •ë�„까지 시간ì�´ 줄어들다니.. ì •ë§� 놀ëž�다. ë�” 줄여ë´�야겠다.
  • ìž�료구조ë�„ 잘 골ë�¼ì•¼ 한다.
  • ì»´í„° ìƒ�태ë�„ 좋아야 한다.--;

8. 최종 결과

  • 17만개짜리 파ì�¼ì—� 쓰는ë�° 6.2ì´ˆ




Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:54
Processing time 0.0065 sec