10989 - 수 정렬하기3 (Radix Sort) [C++]

기수 정렬로 풀어보라해서 기수 정렬로 풀었는데.. 메모리 초과가 계속 떠서 알아봤더니 

기수 정렬로는 못 풀고 카운팅 정렬로만 풀 수 있다고 한다. 카운팅 정렬로 풀어봐야겠다.

#include <iostream>
#include <vector>

using namespace std;

class Radix
{
private:
 vector<int> A, B, C, D, E;
 vector<vector<int>> Bucket;
 int N;
public:
 Radix(int n);
 void Input();
 void Sort();
 void Print();
};

int main()
{
 cin.tie(NULL);

 int N;
 cin >> N;

 Radix R(N);
 R.Input();
 R.Sort();
 R.Print();
}

Radix::Radix(int n)
{
 this->N = n;
 
 for (int i = 0; i < 10; i++)
 {
  vector<int> Temp;
  Temp.push_back(i);
  Bucket.push_back(Temp);
 }
}

void Radix::Input()
{
 for (int i = 0; i < this->N; i++)
 {
  int input;
  cin >> input;

  if (input < 10)
   this->A.push_back(input);
  else if (input < 100)
   this->B.push_back(input);
  else if (input < 1000)
   this->C.push_back(input);
  else if (input < 10000)
   this->D.push_back(input);
  else
   this->E.push_back(input);
 }
}

void Radix::Sort()
{
 // AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
 for (int i = 0; i < A.size(); i++)
  Bucket[A[i] % 10].push_back(A[i]);

 A.clear();
 
 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 1; j < Bucket[i].size(); j++)
   A.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 // BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
 for (int i = 0; i < B.size(); i++)
  Bucket[B[i] % 10].push_back(B[i]);

 B.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   B.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < B.size(); i++)
  Bucket[(B[i] % 100) / 10].push_back(B[i]);

 B.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   B.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 // CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
 for (int i = 0; i < C.size(); i++)
  Bucket[C[i] % 10].push_back(C[i]);

 C.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   C.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < C.size(); i++)
  Bucket[(C[i] % 100) / 10].push_back(C[i]);

 C.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   C.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < C.size(); i++)
  Bucket[(C[i] % 1000) / 100].push_back(C[i]);

 C.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   C.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 // DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
 for (int i = 0; i < D.size(); i++)
  Bucket[D[i] % 10].push_back(D[i]);

 D.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   D.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < D.size(); i++)
  Bucket[(D[i] % 100) / 10].push_back(D[i]);

 D.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   D.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < D.size(); i++)
  Bucket[(D[i] % 1000) / 100].push_back(D[i]);

 D.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   D.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }

 for (int i = 0; i < D.size(); i++)
  Bucket[(D[i] % 10000) / 1000].push_back(D[i]);

 D.clear();

 for (int i = 0; i < Bucket.size(); i++)
 {
  for (int j = 0; j < Bucket[i].size(); j++)
   D.push_back(Bucket[i][j]);

  Bucket[i].clear();
 }
}

void Radix::Print()
{
 for (int i = 0; i < A.size(); i++)
  cout << A[i] << "\n";
 for (int i = 0; i < B.size(); i++)
  cout << B[i] << "\n";
 for (int i = 0; i < C.size(); i++)
  cout << C[i] << "\n";
 for (int i = 0; i < D.size(); i++)
  cout << D[i] << "\n";
 for (int i = 0; i < E.size(); i++)
  cout << E[i] << "\n";
}