[백준 4358] 생태학

문제 풀이

 

단순하게 완전탐색으로는 문제를 해결할 수 없다.

해당 나무의 종이 몇번 등장하는지 알아야 하기 때문에 해당 나무가 있는지 없는지를 빠르게 파악할 수 있어야 한다.

이걸 풀어서 생각해보면 탐색을 O(logN)에 해결하면 쉽게 풀 수 있다.

O(입력받는 나무의 종 10000 x log1000000) => O(60000)

 

탐색을 빠르게 할 수 있으면서 해당 종이 몇 개 있는지 알 수 있는 자료구조는 map이 있다.

해당 나무의 종이 없다면 새롭게 1로 할당하면 되고, 이미 있는 종이라면 그 횟수를 늘리는 식으로 카운팅을 해놓고

해당 나무의 종의 개수 / (전체 입력 수) * 100을 하게 되면 해당 나무의 % 비율을 계산할 수 있게 된다.

 

나무 종의 이름이 공백을 포함한 형태이기 때문에 공백을 포함해서 문자열을 입력받아야 한다.

또한, 입력이 끝났는지를 판별하는 eof 개념도 알고 있어야 한다.

 

소스 코드

 

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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    string tree;
    map<string, int> mp;
    double cnt = 0;
    while(getline(cin, tree))
    {
        mp[tree]++;
        cnt++;
    }
    
    cout << fixed;
    cout.precision(4);
    for(const auto& m : mp)
    {
        //몇 %를 차지하는지 나타내기 위해서는 x100을 해야한다.
        cout << m.first << ' ' << m.second / cnt * 100 << '\n';
    }
    return 0;
}