글 읽기 - 기수정렬으로 메모리초과

akssus 7년 전 0

카운팅 정렬(Counting Sort) 혹은 기수 정렬(Radix Sort)를 사용해 봅니다

라고 써있는데.. 카운팅소트로는 풀었는데

기수정렬으로 해볼려고 하는데 뜨는 메모리초과를 어떻게 잡아야 할까요?

#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

queue<int> qArr[10];
queue<int> input;
int g_maxCipher = 0;

int getCipher(int val)
{
    int cipher = 0;
    while(val != 0)
    {
        val /= 10;
        cipher++;
    }
    return cipher;
}

int getCipherValue(int val,int cipher)
{
    int rVal = 0;
    rVal = int(val/pow(10,cipher-1))%10;
    return rVal;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int k;
        scanf("%d",&k);
        input.push(k);
        g_maxCipher = max(g_maxCipher,getCipher(k));
    }
    
    for(int c=1; c<=g_maxCipher; ++c)
    {
        while(!input.empty())
        {
            int val = input.front();
            input.pop();
            int cipherVal = getCipherValue(val,c);
            qArr[cipherVal].push(val);
        }
        
        for(int i=0; i<10; ++i)
        {
            while(!qArr[i].empty())
            {
                int val = qArr[i].front();
                qArr[i].pop();
                input.push(val);
            }
        }
    }
    while(!input.empty())
    {
        int val = input.front();
        input.pop();
        printf("%d\n",val);
    }
   
   return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

기수정렬으로 메모리초과

akssus 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말