수 정렬하기 3

solved_ac[Class2][수 정렬하기 3](https://www.acmicpc.net/problem/10989)

문제

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

문제 해석

앞서 풀었던 [백준]2751번: 수 정렬하기 2 문제와 비슷하다. 하지만 2751번에서 설명한 sort 알고리즘을 가지고 풀면 안된다. 입력 받는 숫자의 max값이 적당히 낮다면 counting sort 알고리즘을 생각해보자.

카운팅 정렬(Counting sort)

• 지금까지 배워온 정렬은 두 수의 대소를 '비교'하는 과정을 거쳐 정렬하는 comparison sort
• 두 수를 반복적으로 비교해 정렬하는 comparison sort는 아무리 알고리즘을 잘 짜도 계산 복잡성이 O(nlogn) 보다 크다.
• 예를 들어 퀵 정렬(quick sort)의 계산 복잡성이 O(n^2)이고, 힙 정렬(heap sort)이 O(nlogn)이라는 점을 감안하면 이 같은 내용이 들어맞음을 확인할 수 있다.
• 하지만 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산 복잡성을 O(n) 선까지 낮추려는 알고리즘이다.
• 여러 숫자들이 리스트에 쌓이게 된다면 리스트 안의 value 들을 건들이는 것이 아닌 새로운 정렬을 선언해 index에 접근한다.
• [2, 3, 3]의 정렬이 있다면 cnt_sort 라는 list를 만들어 index 2에 접근해 1을 올려주고 index 3에 접근해 2를 올려준다.
• 나머지 index에 해당하는 value들은 0으로 초기화를 시켜준다.
• 그렇게 루프를 돌려서 value가 0이 아닌 index의 value들만 출력하게 되면 오름차순 정렬이 되는것이다.

시간 복잡도

• 전체적인 계산 복잡성은 O(n + max)가 된다. max가 충분히 작을 경우 O(n)이 되지만, max가 커질 경우 좋은 알고리즘이 아니다.

첫번째 풀이

• 숫자들을 입력받아서 list에 넣어준다.
• sort(reverse = False)를 써서 오름차순 정렬을 해준다.

import sys

N = int(sys.stdin.readline())

num_sort = []

for i in range(N):
    num_sort.append(int(sys.stdin.readline()))
    
num_sort.sort(reverse = False)

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

틀린 이유

• for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용하지 못하게 된다.
• 일반적으로 입력 값이 크지 않은 경우에는 상관없지만 입력값이 극한으로 주어질 때는 메모리를 좀 더 효율적으로 관리해야한다.
• 그렇지 않으면 메모리 초과 오류가 뜨게 된다.

두번째 풀이

• counting sort 알고리즘을 사용한다.
• 숫자는 아무리 커봐야 10000이라고 주어졌으니 10001개의 list를 0으로 초기화 한다.
• 루프를 돌면서 입력 받은 숫자를 index에 접근하여 해당 index의 value 값을 +1 해준다.
• 10001번의 루프를 다시 돌면서 list의 value 값이 0이 아닌것만 출력해주면 index는 0부터 시작하기 때문에 알아서 오름차순 정렬이 된다.

import sys

N = int(sys.stdin.readline())

cnt_sort = [0] * 10001

for i in range(N):
    cnt_sort[int(sys.stdin.readline())] += 1
    
for i in range(len(cnt_sort)):
    if cnt_sort[i] != 0:
        for j in range(cnt_sort[i]):
            print(i)