[알고리즘/정렬] 백준 BOJ 10989 수 정렬하기 3

7. BOJ 10989 수 정렬하기 3

10989번: 수 정렬하기 3

 

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

 

 

---

💡나의 문제 풀이

작성 코드

import sys

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

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
	count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정보 확인
	for j in range(count[i]):
		print(i)

 

답안 코드

• 계수 정렬에서 사용하는 방법을 사용해야 한다.

import sys

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

for _ in range(n):
  tmp = int(sys.stdin.readline())
  count[tmp] += 1

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

 

---

 

리뷰 및 점검

• 앞선 수 정렬하기 1,2 문제와 다른 점이 “제한된 메모리 크기”이다.
• 10,000,000개의 수가 입력될 수 있고, 10,000 이하의 숫자라는 점, 그리고 동일한 숫자가 반복되는 경우를 고려하면 일반적인 리스트에 수를 전부 담기는 어렵기 때문에 미리 10,001개의 리스트를 0으로 초기화한 후 몇번 반복됐는지에 따라 그 count값을 증가하는 방법을 사용해야 한다.