[백준] 수 정렬하기3(10989번)-Python

문제

---

 

 

✅중요 개념

---

계수 정렬 ( Counting Sort ) 

    계수 정렬이란 sort 메소드를 이용하는 것이 아니라 정렬하려는 List의 값 중 가장 큰 값을 List의 size + 1을 크기로 가지는 List를 생성하여 index를 정렬하는 숫자의 해당 숫자로 사용하여 Sorting을 하는 방법을 말한다.

👍자세한 내용은 링크를 참고해 주세요 -- https://www.programiz.com/dsa/counting-sort

Counting Sort (With Code in Python/C++/Java/C)

 

✅코드

---

import sys

input = sys.stdin.readline

countingSort = [0]*10001
num = int(input())

for _ in range(num):
    countingSort[int(input())] += 1

for i in range(10001):
    if countingSort[i] > 0:
        for _ in range(countingSort[i]):
            print(i)

 

코드 설명

숫자의 최대 크기가 10000 이기 때문에 index를 해당 숫자로 사용하기 위해서 10000 + 1을 크기로 가지는 countingSort List를 만들어 준다.

이 때 countingList의 index가 입력 받은 숫자의 값이 된다.

num 횟수 만큼 숫자를 입력 받아 해당 index의 값을 1 증가 시킨다.

ex) 8을 입력 받으면 countingSort[8]의 값을 1 증가 시킨다.

 

countingSort List를 순회하며 값이 0 보다 큰 경우 countingSort[index]의 값 만큼 해당 index를 출력한다.

 

✅주의 사항

---

1. 해당 개념은 Counting Sort의 일부 개념만을 차용해 적용한 것이다. 👍꼭 ! 위의 링크를 통하여 개념을 이해하시길 바라겠습니다. ( 참고로 모든 개념을 사용하면 메모리초과 오류가 발생합니다..)

 

2. pypy3가 아닌 Python3로 제출하시기 바랍니다.

    python3가 pypy3보다 메모리제한이 높기 때문입니다. 대신 pypy3는 python3보다 속도가 빠릅니다.