글 읽기 - C++ 기수 정렬으로 '틀렸습니다'가 뜹니다..

gusdn6763 3년 전 1

큐와 데큐를 이용해서 문제를 풀었습니다. 예제를 많이 돌려봐도 정상적으로 출력하는데 반례를 못 찾겠습니다...

#include<iostream>
#include<queue>
#include<deque>
#include<cmath>

using namespace std;

int main(void)
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    queue<int> PQ[10];
    deque<int> NQ[10];
    int Arr[1000001] = { 0 };
    int count, maxDigit = 0, digit = 1, N;

    cin >> count;
    for (int i = 0; i < count; i++)
    {
        cin >> Arr[i];
        if (Arr[i] < 0)
        {
            maxDigit = max(-Arr[i], maxDigit);
        }
        else
        {
            maxDigit = max(Arr[i], maxDigit);
        }
    }
    while (maxDigit > 10)
    {
        maxDigit /= 10;
        digit++;
    }
    for (int i = 0; i < digit; i++)
    {
        for (int j = 0; j < count; j++)
        {
            if (Arr[j] < 0)
            {
                N = -Arr[j] / (int)pow(10, i) % 10;
                NQ[N].push_back(Arr[j]);
            }
            else
            {
                N = Arr[j] / (int)pow(10, i) % 10;
                PQ[N].push(Arr[j]);
            }
        }
        int idx = 0;
        for (int j = 9; j > -1; j--)
        {
            while (NQ[j].empty() == false)
            {
                Arr[idx] = NQ[j].front();
                NQ[j].pop_front();
                idx++;
            }
        }

        for (int j = 0; j < 10; j++)
        {
            while (PQ[j].empty() == false)
            {
                Arr[idx] = PQ[j].front();
                PQ[j].pop();
                idx++;
            }
        }
    }
    for (int i = 0; i < count; i++)
    {
        cout << Arr[i] << "\n";
    }
    return (0);
}

BaaaaaaaaaaarkingDog 3년 전 1

-1000

-100000

일 때 이상해요

gusdn6763 3년 전 0

자릿수를 하나더 적게 체크하는거 체크 했습니다. 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

C++ 기수 정렬으로 '틀렸습니다'가 뜹니다..

gusdn6763 3년 전 1

BaaaaaaaaaaarkingDog 3년 전 1

gusdn6763 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말