백준 4358번 : 생태학

문제 접근

---

저번에 '백준 5052번 : 전화번호 목록' 풀고, 트라이 알고리즘을 익히려고 문제를 찾던 중 이 문제를 풀게 되었다.

 

처음에문제를 보고 set 을 사용하면 될 것 같아서 구조 잡다가 map <string, int> 로 풀면 안 되는지 아주 잠깐 고민했다. 그런데 이미 주제를 알고있어서 그런지 트라이로 풀어야되는거면 당연히 안 되겠다 싶어서 5052번 코드 가져와서 수정했다.

 

공백과 특수문자가 포함되는 경우도 있다고 해서, 아스키 코드값 기준 32~126 까지 사용 가능하도록 했다. 종결되는 시점에서 count 값을 1 증가시키고, find 함수를 통해 종결되는 시점의 count 값을 가져오도록 구현했다. 시간 복잡도는 O(문자열의 개수 * 문자열의 최대 길이) 로 O(1,000,000*30) 이다.

 

다 풀고, 다른 사람들 풀이보니까 코드가 내 코드의 반절이어서 확인해봤다. 그냥 map 으로 풀었던데, 트라이로 푼다는 고정 관념에 잡혀서 이 풀이를 그냥 지나쳤다. 어차피 트라이 연습하려고 한거니까 목적은 달성했다.

근데 map 으로 푼 코드, 시간 복잡도 계산해보니까 O(1,000,000*log30) 이네.. 헤헤..

 

rate 에 값 넣어줄 때, cstring 의 strcpy 안 써서 string 헤더 하나로 해결하고 싶었는데 *iter 로 불러온 string 이어서 그런지 안 된다. 다르게 구현하는 방법은 많겠지만 그냥 간단하게 끝냈다.

 

알게 된 내용

1. c++ 에서 출력때 소수점 고정하려면, cout<<fixed; cout.precison(n) 을 사용한다.

2. 자료형의 type 을 알고 싶다면, #include <typeinfo> 헤더 선언한 후, type(자료형).name 으로 확인할 수 있다.

 

 

 

문제 코드

---

#include <iostream>
#include <set>
#include <string>
#include <cstring>

using namespace std;

const int STR = 95;

struct TrieNode
{
	TrieNode* children[STR];
	bool terminal;
	int count;
	
	TrieNode():terminal(false),count(0)
	{
		for(int i=0; i<STR; ++i)
			children[i] = nullptr;
	}
	
	~TrieNode()
	{
		for(int i=0; i<STR; ++i)
			if(children[i] != nullptr)
				delete children[i];
	}
	
	void insert(char* s)
	{
		if(*s == '\0')
		{
			terminal = true;
			++count;
		}
		
		else
		{
			int next = *s - 32;
			if(children[next] == NULL)
				children[next] = new TrieNode();
			children[next]->insert(s+1);
		}
	}
	
	int find(char* s)
	{
		if(terminal && *s == '\0')
			return count;
		
		int next = *s - 32;
		return children[next]->find(s+1);
	}
};

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int total = 0;
	char treeSpecies[30];
	set<string> treeList;
	
	TrieNode* root = new TrieNode();
	
	while(cin.getline(treeSpecies, 30))
	{
		treeList.insert(treeSpecies);
		root->insert(treeSpecies);
		++total;
	}
	
	for(auto iter = treeList.begin(); iter != treeList.end(); ++iter)
	{
		string s = *iter;
		
		double rate = (double)root->find(strcpy(treeSpecies,s.c_str()))/(double)total * 100;
		
		cout<<fixed;
		cout.precision(4);
		cout<<s<<' '<<rate<<'\n';
	}
	
	delete root;
}