[백준 2751번 문제, 파이썬3] 수 정렬하기 2

문제

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

2751번: 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

코드

일반적인 파이썬 정렬 코드이다

import sys
count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
for i in sorted(my_list):
    print(i)

---

해결

음.. 뭔가 이상하다

 

처음 맞췄던 방법은 출제자가 의도한 방법이 아닌것 같아서 병합정렬이랑 계수정렬을 사용해서 코드를 작성했는데

틀렸거나 시간초과 결과가 나온다... 이상하다 

 

병합정렬

import sys


def mergeSort(A, p: int, r: int):
    if p < r:
        q = (p + r) // 2
        mergeSort(A, p, q)
        mergeSort(A, q + 1, r)
        merge(A, p, q, r)


def merge(A, p: int, q: int, r: int):
    i = p
    j = q + 1
    t = 0
    tmp = [0 for i in range(len(A))]
    while i <= q and j <= r:
        if A[i] <= A[j]:
            tmp[t] = A[i]
            i += 1
        else:
            tmp[t] = A[j]
            j += 1
        t += 1
    while i <= q:
        tmp[t] = A[i]
        i += 1
        t += 1
    while j <= r:
        tmp[t] = A[j]
        j += 1
        t += 1
    i = p
    t = 0
    while i <= r:
        A[i] = tmp[t]
        i += 1
        t += 1


count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
mergeSort(my_list, 0, len(my_list) - 1)
for i in my_list:
    print(i)

 

계수정렬

import sys


# 계수 정렬
def counting_sort(A: list):
    k = max(A)
    c = [0 for _ in range(k + 1)]
    for j in range(len(A)):
        c[A[j]] += 1
    for i in range(1, k + 1):
        c[i] += c[i - 1]
    b = [0 for _ in range(len(A))]
    for j in range(len(A) - 1, -1, -1):
        b[c[A[j]] - 1] = A[j]
        c[A[j]] -= 1
    return b


count = int(sys.stdin.readline())
my_list = [int(sys.stdin.readline()) for _ in range(count)]
for i in counting_sort(my_list):
    print(i)

 

그런데 왜 다 틀렸다고 뜨는거지... 이유를 알수가 없구만

---

참고

링크