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

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

10989번: 수 정렬하기 3

 

• N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하기

• 입력
  • 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어짐
  • 둘째 줄부터 N개의 줄에는 수가 주어짐
  • 이 수는 10,000보다 작거나 같은 자연수
• 출력
  • 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력
• 시간 제한: 5초
• 메모리 제한: 8 MB

 

"""
입출력 예시)

10
5
2
3
1
4
2
3
5
1
7
    -> 1
       1
       2
       2
       3
       3
       4
       5
       5
       7
"""

 

 

## 의사코드 ##

# 오름차순 정렬
#sort()

 

 

 

첫 번째 시도

 

n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))

nums.sort()
for i in nums:
    print(i)

 

-> 메모리 초과로 실패

 

 

 

통과한 코드

 

import sys
input = sys.stdin.readline
num = int(input())
arr = [0]*10000 # 입력으로 받을 수 있는 10,000개의 수를 담을 수 있는 배열

# 입력받을 때마다 그 수에 해당하는 인덱스에 +1을 한 값으로 그 수의 개수 담기
for i in range(num):
    a = int(input())
    arr[a-1] += 1

# 배열을 돌면서 값이 0이 아닌 경우, 값만큼 인덱스에 해당하는 숫자를 출력
for i in range(10000):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i+1)

 

-> 계수정렬 활용

 

 

• 계수정렬의 정렬 과정
  • 1) 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있는 배열 생성
  • 2) 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
  • 3) 증가된 배열에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력

 

 

 

 

 

참고)

 

https://computer-science-student.tistory.com/587

[알고리즘] 계수 정렬(Counting Sort)

 

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC

[파이썬python] 백준 10989번 - 메모리 초과