백준 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

 

 

🍃 풀이

1) 틀린 답 (메모리 초과)

N = int(input())
num_list = []

for _ in range(N):
    num = int(input())
    num_list.append(num)

sorted_list = sorted(num_list)

for num in sorted_list:
    print(num)

- sort, sorted() 사용 했었음.

- 입력값이 극한으로 많이 주어질 때에는 메모리를 효율적으로 관리해야함.

 

 

2) 틀린 답 퀵정렬 사용(메모리 초과)

N = int(input())

num_list = []

for _ in range(N):
    num = int(input())
    num_list.append(num)

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)


for num in quick_sort(num_list):
    print(num)

- 퀵 정렬은 매우 큰 입력값을 처리할 땐 메모리 초과가 발생할 수 있다.

 

 

🍃 정답

import sys

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

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

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

계수정렬(counting sort)

- 특정한 조건이 부합할 때, 배열 원소 간 비교하지 않고 정렬하는 알고리즘이다.

- 특정한 조건이란, 원소들이 정수이며 0~K(K=정수)의 범위 안에 포함될 때를 가정한다.

- O(N+K)의 시간, 공간 복잡도를 가진다.

- 만약 최댓값 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다.

 

제약조건

- 데이터는 양수여야한다.

- 값의 범위가 너무 크지 않아야 한다.(메모리 사이즈를 넘어서는 안된다.)

 

장점

알고리즘에서 데이터 간 비교를 수행하지 않기 때문에 O(N)의 시간 복잡도의 성능을 보여준다.

• 이는, 기존에 우수한 정렬 알고리즘으로 평가받는 퀵 정렬, 병합 정렬 O(NlogN) 보다 더 빠르다.

데이터가 정수 표현이 가능하고, 데이터 간 차이가 크지 않을 때 유리하다.

 

단점

많은 메모리 공간을 필요로 한다.(K 크기의 배열을 만들어야 한다.)

• ex) 데이터가 5개 존재하는데 각각 0, 3, 2, 1, 1000000 이라면? 단 아닐때는 유리하다.