본문 바로가기

알고리즘 관련/BOJ

BOJ)2910 빈도 정렬

문제: icpc.me/2910


수열이 존재할 때 수열에서 가장 많이 등장하는 빈도로 정렬을 하는 문제이다.


이 때 빈도가 같은 수는 먼저 등장한 순서대로 정렬을 해야한다.


우리는 수가 최대 10억까지 들어올 수 있으므로 빈도를 저장하기 위해 키값에 따른 값을 저장할 수 있는 map 자료 구조를 사용할 수 있다.


두개의 맵을 선언하여 하나는 빈도수를 하나는 들어온 순서를 저장한 뒤 


벡터에 빈도수와 키값을 삽입 시켜준 뒤 조건에 맞게 정렬을 해준 뒤 출력해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int n, c, x;
map<intint> mp;
map<intint> m;
vector<pair<intint>> p;
bool cmp(pair<intint> a, pair<intint> b) {
    if (a.first == b.first) {
        return m[a.second] < m[b.second];
    }
    return a.first > b.first;
}
int main() {
    scanf("%d%d"&n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d"&x);
        mp[x]++;
        if (!m[x])
            m[x] = i + 1;
    }
    for (auto i : mp) 
        p.emplace_back(i.second, i.first);
    sort(p.begin(), p.end(), cmp);
    for (auto i : p) {
        for (int j = 0; j < i.first; j++)
            printf("%d ", i.second);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13913 숨바꼭질4  (0) 2017.01.17
BOJ)13549 숨바꼭질3  (0) 2017.01.17
BOJ)7795 먹을 것인가 먹힐 것인가  (0) 2017.01.15
BOJ)3758 KCPC  (0) 2017.01.15
BOJ)8983 사냥꾼  (0) 2017.01.15