[알고리즘문제] 백준 생태학

www.acmicpc.net/problem/4358

4358번: 생태학

나무를 나무의 분포도를 출력하는 문제

문자열을 입력받고 해당 문자열이 총 얼마나 나왔는지 백분율로 계산하여 소수점 4자리까지 반올림하여 출력하는 문제이다.

#include<iostream>
#include<string>
#include<map>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	map<string, float> m;
	string treeName;
	float total = 0;
	while (getline(cin, treeName)) {
		total++;
		if (m.find(treeName) == m.end()) {
			m[treeName] = 1;
		}
		else {
			m[treeName] += 1;
		}
	}
	cout << fixed;
	cout.precision(4);
	for (auto it = m.begin(); it != m.end(); it++) {
		cout << it->first << " " << (it->second / total) * 100 << endl;
	}
	
	return 0;
}

getline으로 문자열을 받고,

map에 문자열과 해당 문자열의 등장 빈도를 value로 저장 시킨다.

cout << fixed; cout.percision(4);로 소수점 고정시킨다.

map을 순회하며 각각 문자열에 대한 등장빈도를 백분률로 계산하여 출력시킨다.

 

시간 복잡도 : O(n)

공간 복잡도 : O(n)