[2910번] 빈도 정렬

문제 출처 :

https://www.acmicpc.net/problem/2910

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구조체 배열

2. 정렬 방식

일단 예제 입력처럼 구조체 배열 중 값에 해당하는 부분에 입력값을 받아들이고,

그다음 구조체를 카운트 해주는 부분에 같은 값이 있으면 cnt를 ++해주는 형식으로 for문을 한번 돌린다.

그다음 카운트가 1이상인 아이들을 tmp구조체 배열에 모두 다 넣고 버블정렬로 num에 대해 정렬하여 출력한다.

값을 받고 -> 값이 몇개있는지 정렬하지 않은 채 카운트를 확인하고 -> 카운트에 대해 정렬하고 -> 출력하는것이 핵심이다.

이때 버블정렬을 쓴 이유는, 최악의 상황이 어디까지인지 확인 해 보고싶었기에 버블 정렬을 이용해 보았고, 

stable sort 혹은 std::sort , quick sort 등등으로도 해결이 모두 가능하다.

참고내용

Stable Sorting ::

 둘 이상의 키로 이루어진 데이터를 정렬 할 때 정렬 대상 이외의 값들은 위치를 유지하는 것이 Stable Sorting이다.

퀵 정렬

　정렬 기준이 맨 처음 원소라면 stable하다.

　그렇지 않다면? 정렬 기준과 원래 원소의 위치를 고려해야 한다.

버블 정렬

　stable 

삽입 정렬

　stable

병합 정렬

　stable 

힙 정렬

　stable 하지 않다.

　순서 정보가 힙에 들어가는 과정에서 파괴됨

소스 코드 : 

#include <iostream>
#include <algorithm>
#include <stdio.h>
 
using namespace std;
 
 
struct _map
{
    long long int num;
    int cnt;
};
 
bool comp_m(_map const &a, _map const &b)
{
    return a.cnt > b.cnt;
}
 
_map m[1001];
_map tmp[1001];
long long int c, val;
 
 
void BubbleSort(_map arr[], int n)
{
    int i, j;
    int temp;
 
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < (n - i) - 1; j++)
        {
            if (arr[j].cnt < arr[j + 1].cnt)
            {
                temp = arr[j].cnt;
                arr[j].cnt = arr[j + 1].cnt;
                arr[j + 1].cnt = temp;
                temp = arr[j].num;
                arr[j].num = arr[j + 1].num;
                arr[j + 1].num = temp;
 
            }
        }
    }
}
 
int main()
{
 
    int n, j = 0, k = 0;
 
    scanf("%d %lld", &n, &c);
 
    // 초기화
    for (int i = 0; i < n; i++)
    {
        m[i].num = 0;
        m[i].cnt = 0;
        tmp[i].num = 0;
        tmp[i].cnt = 0;
    }
 
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &val);
        m[i].num = val;
 
        // 같은 넘버 있으면 그넘버 cnt++
        for (j = 0; j <= i; j++)
        {
            if (m[j].num == m[i].num)
            {
                m[j].cnt++;
                break;
            }
        }
    }
 
    j = 0;
    for (int i = 0; i < n; i++)
    {
        if (m[i].cnt != 0)
        {
            tmp[j].num = m[i].num;
            tmp[j].cnt = m[i].cnt;
            j++;
        }
    }
    
    BubbleSort(tmp, j);
 
 
    // tmp 배열의 cnt가 0이 될때까지 계속 출력
    for (int i = 0; i < j; i++)
    {
        while (tmp[i].cnt > 0)
        {
            tmp[i].cnt--;
            printf("%lld ", tmp[i].num);
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>