백준#10989 수 정렬하기 3

문제

풀이

나의 풀이

• 나의 풀이1
  

import sys


num_count = int(input())

array = list()
for _ in range(num_count):
    array.append(int(sys.stdin.readline()))

result = sorted(reverse=True)
for item in result:
    print(item)

• 나의 풀이2
  

import sys


num_count = int(input())

array = list()
nums_under_5000 = list()
nums_over_5000 = list()
for _ in range(num_count):
    num = int(sys.stdin.readline())
    if num < 5000:
        nums_under_5000.append(num)
    else:
        nums_over_5000.append(num)

for num in sorted(nums_over_5000, reverse=True):
    print(num)
for num in sorted(nums_under_5000, reverse=True):
    print(num)

*나의 풀이

import sys


num_count = int(input())

result = [0 for x in range(10001)]
for _ in range(num_count):
    num = int(sys.stdin.readline())
    result[num] += 1

for i in range(0, 10001):
    for _ in range(result[i]):
        print(i)

남의 풀이

• 1천만개 미만의 경우 계수 정렬 알고리즘을 파이썬에 적용할 수 있음

  계수 정렬(Couting Sort) 알고리즘

• 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
• 배열의 크기를 데이터의 범위를 포함할 수 있도록 설정
• 데이터가 등장한 횟수를 센다
• 남의 풀이

import sys


n = int(sys.stdin.readline())
array = [0] * 10001

for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
    if array[i] !=0 :
        for j in range(array[i]):
            print(i)

느낀 점

• 파이썬은 약 1초에 천만개의 연산을 수행할 수 있음

Reference

• https://www.acmicpc.net/problem/10989