글 읽기 - radix sort 시간초과

sangw0804 5년 전 0

음수와 양수로 나눈 뒤 radix sort를 이용해서 정렬하려고 했는데 시간 초과가 뜨네요... radix sort로는 못 푸는 문제인건지 아니면 제가 구현을 잘못한건지 모르겠네요 ㅜㅠ 고수분들 도와주세요

import sys
from functools import reduce

minusNums = []
plusNums = []

[n, k] = [int(_) for _ in sys.stdin.readline().split(' ')]

tempNums = sys.stdin.readline().split(' ')
for i in range(len(tempNums)):
    num = int(tempNums.pop())
    plusNums.append(num) if num >= 0 else minusNums.append(num)


def getDigitNum(num):
    result = len(str(num))
    return result if num >= 0 else result - 1


def getLargestDigitNum(arr):
    largest = -1
    for num in arr:
        largest = max(largest, getDigitNum(num))
    return largest


def getDigit(num, index):
    return (abs(num) // (10 ** index)) % 10


def radixSort(nums):
    buckets = [[] for _ in range(10)]
    iterCount = getLargestDigitNum(nums)
    for i in range(iterCount):
        for num in nums:
            buckets[getDigit(num, i)].append(num)
        nums = reduce(lambda accu, cur: accu + cur, buckets)
        buckets = [[] for _ in range(10)]
    return nums


if k <= len(minusNums):
    sortedList = radixSort(minusNums)
    print(sortedList[-k])
else:
    sortedList = radixSort(plusNums)
    print(sortedList[k - len(minusNums) - 1])

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

문제

문제

출처

ICPC

radix sort 시간초과

sangw0804 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말