[백준] 4358 생태학 (C++)

백준 4358 생태학

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

입력받을 나무의 개수가 주어져 있지 않아서 찾아보니 geline(cin, str)을 사용하여 while문을 돌리면 끝까지 받을 수 있었다. 

 

1. 전체 나무에서 각 나무들이 차지하는 비율을 구해야 하므로 cnt를 증가시키면서 전체 나무 수를 구하고

2. map을 사용하여 나무 이름과 해당 나무의 개수를 담는다. 이때, map은 자동으로 오름차순 정렬이 되므로 따로 사전 순으로 정리할 필요는 없다.

3. 입력받은 나무가 map에 존재하면 해당 나무의 개수를 1증가시키고, 존재하지 않으면 1로 업데이트시킨다.

4. 소수점 4자리까지 구해주기 위해

  cout << fixed를 사용하여 소수점을 고정시키고

  cout.precision(4) 을 사용하여 4자리까지 출력시킨다.

5. 마지막에 map의 크기만큼 for문을 돌리면서 각 나무의 비율을 구해준 후에 나무이름과 비율을 출력시킨다.

3. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;

map<string, float> tree;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string str;
    float cnt = 0;
    float ans = 0;
    while (getline(cin, str))
    {
        cnt++;
        auto item = tree.find(str);
        //str이 tree에 존재한다면 해당 요소가 출력, 
        //그렇지 않으면 tree.end()를 반환시킴

        //존재하는 경우
        if (item != tree.end())
        {
            tree[str] += 1;
        }
        //존재하지 않는 경우
        else
        {
            tree[str] = 1;
        }
    }
    //소수점 고정
    cout << fixed;
    //소수점 4자리까지만 출력
    cout.precision(4);

    for (auto it = tree.begin(); it != tree.end(); ++it)
    {
        ans = (it->second / cnt) * 100;
        cout << it->first << " ";
        cout << ans << "\n";
    }
    return 0;
}

4. 시간 복잡도

입력받는 나무의 개수만큼 수행된다.

5. 결과