백준 4358 생태학 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/4358

아이디어

• 자료구조 map 사용
• 각 나무를 맵에 넣은다음에 추가될때마다 카운트 증가
  • 나무의 키들을 뽑아 정렬
  • 전체 개수중에 각 나무의 카운트를 출력

시간복잡도 계산

• 맵에 넣기 O(M)
• 맵 키 정렬O(NlgN)
• 각 나무의 카운트를 출력

인트 계산

• 최대 나무개수 e6 가능

코드

#include <iostream>
#include <string>
#include <map>
#include <cmath>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    map<string, int> tree;
    int cnt=0;
    
    string s;
    while(getline(cin, s)) {
        cnt++;
        tree[s]++;
        
    }
    cout <<fixed;
    cout.precision(4);
    
    for(auto it = tree.begin(); it !=tree.end(); it++) {
        cout << it->first << ' ' << round(it->second/(double)cnt*1000000)/10000 << '\n';
    }
    return 0;
}
 
 
 

문제유형

• 자료구조 - map