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

유형 : 정렬

[예제]

10
5
2
3
1
4
2
3
5
1
7

[출력]

1
1
2
2
3
3
4
5
5
7

---

1. 내 풀이(틀림)

N = int(input())

num_list = []
for _ in range(N):
    tmp = int(input())
    num_list.append(tmp)

num_list = sorted(num_list)

for i in range(N):
    print(num_list[i])

▷ 메모리 초과로 실패

▷ 기본 정렬 라이브러리로는 안 되는 듯 하다.

▷ 반복문 안에 append를 썼기 때문에 메모리 재할당이 일어나 속도 저하와 비효율적인 메모리 사용이 발생한다. (출처)

▷ FAQ : https://www.acmicpc.net/board/view/26132

모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다.

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

** 핵심 아이디어
1. 데이터 개수가 최대 10,000,000개
2. 시간 복잡도가 O(N)인 정렬 알고리즘을 이용
3. 수의 범위가 1 ~ 10,000이므로 계수 정렬 이용

 

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

- 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
- 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정

- 데이터가 등장한 횟수를 셈

- 유의사항 : 데이터의 개수가 많을 때 파이썬에서는 sys.stdin.readline()를 사용해야 함

ex. [3,3,7]

- 3이 2번 등장 : 3의 인덱스는 2

- 7이 1번 등장 : 7의 인덱스는 1
→ 앞에서부터 진행해서 수 하나씩 등장할 때마다 인덱스를 하나씩 증가

 

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)

문제 출처 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3