[백준][Python] 10989. 수 정렬하기 3

 

 

 

 

 

 

🙆‍♂️문제

---

 

 

🙋‍♂️풀이

---

이번 문제는 계수 정렬을 활용해서 푸는 문제입니다.

 

 

🚀 입력받기

---

import sys
n= int(sys.stdin.readline())
arr = [int(sys.stdin.readline())for _ in range(n)]

sys 라이브러리를 import 하여 더 빠르게 입력되어서 시간 초과가 되지 않도록 했습니다.

 

 

🚀 계수 정렬

---

def countSort(arr):
    length = len(arr)
    minNum = min(arr)
    maxNum = max(arr)

    #카운팅 배열 구하기
    alpha = maxNum - minNum + 1
    cntArr = [0]*alpha

    for i in arr:
        j = i - minNum
        cntArr[j]+=1

    #누적 카운팅 배열 구하기
    accArr = []
    accCnt=0
    for i in cntArr:
        accCnt+=i
        accArr.append(accCnt)

    #최종 인덱스 배열 구하기
    endIdxArr = [a-1 for a in accArr]

    #정렬 배열 구하기
    sortArr = [0]*length
    for i in reversed(arr):
        cntIdx = i - minNum
        endIdx = endIdxArr[cntIdx]
        sortArr[endIdx] = i
        endIdxArr[cntIdx]-=1

    return sortArr

sortArr = countSort(arr)

카운팅 정렬 함수를 만들어서 사용했습니다. 

자세한 내용은 계수 정렬 이 곳에 정리되어 있습니다.

 

🚀 출력하기

---

for i in sortArr:
    print(i)

반복문을 사용하여 정렬된 배열을 출력했습니다.

 

그런데 이제 이렇게 하면 메모리 초과가 납니다. 그래서 엄청나게 축약시켜줍니다.

 

import sys
n= int(sys.stdin.readline())

cntArr = [0]*10001
for i in range(n):
    cntArr[int(sys.stdin.readline())] +=1

for i in range(len(cntArr)):
    for j in range(cntArr[i]):
        print(i)

최종 코드 입니다.