백준 생태학 [c++]

4358 생태학 실버2

문제 링크

문제

생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다.

입력

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다.

출력

주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다.

풀이

처음에는 vector<string, float>에 나무의 종과 1을 입력받고,
이후 정렬한 후 같은 부분이 있으면 float을 늘려주고 중복되는 걸 지우면서 해결하려 했다.
실행결과는 맞게 나오나 시간초과.
vector를 사용한 풀이에서 더 이상 줄일 부분이 없는 것 같아, 풀이를 찾아봤다.

찾아보니 C++에서 map과 vector의 차이점을 알 수 있었다.

map과 vector의 차이

map은 key value를 가지는 자료구조이고, vector는 원하는 형식을 집어넣을 수 있는 컨테이너이다.
둘 다 비슷한 함수를 가지고 있다.

입력이 매우 많은 경우 vector보다 map이 유리하다고 한다.
또한 map의 장점은 map은 기본적으로 오름차순 정렬이 되어 이 문제와 적합하다.(내림차순도 가능 : map <int, int, greater> map1;)

vector를 map으로 바꾸고 iterator를 사용해 출력하니, 시간초과 해결할 수 있었다.

코드

#include <iostream>
#include <string.h>
#include <map>
#include <iterator>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    map<string, float> species;
    string in;
    int sum = 0;

    getline(cin, in);
    while(in.size() != 0){
        // species.push_back(make_pair(in, 1.0000));
        species[in]++;
        sum++;
        getline(cin, in);
    }
    
    map<string, float>::iterator iter;
    cout << fixed;
    cout.precision(4);

    for(iter = species.begin(); iter != species.end(); ++iter)
    {
        cout << iter->first << " " << iter->second * 100 / sum << "\n";
    }


    return 0;
}

• ps
• string
• map