오늘의 알고리즘(4월 29일)

1. 백준, 수 정렬하기3, 10989번

 

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

---

2. 생각해보자

• 첫 입력값 N은 앞으로 입력될 정수의 개수 
• N개의 입력값을 array에 입력받는다.
• 파이썬 기본 정렬 알고리즘을 사용하여 오름차순 정렬 후 한개씩 출력한다. 

n = int(input())
array = []

for _ in range(n):
    data = int(input())
    array.append(data)

array.sort()

for data in array:
    print(data)

 

- 결과는 올바르게 나오지만 백준 채점 결과, 메모리 또는 시간초과가 뜬다. 

- 아무래도 입력값이 많을 때에는 시간복잡도가 좋지 않아서 그런 것 같다. 어떻게 해결할까? 

---

3. 해설 및 분석

• 문제를 보면, data가 최대 1000만개 까지 나올 수 있다고 명시되어 있다.
• 더불어, 주어지는 수는 10,000보다 작거나 같은 자연수가 나온다고 되어 있다. 
• 주어지는 데이터의 개수는 많지만 각 데이터의 범위는 작은 문제이다.  
• 파이썬은 대략적으로 1초에 2천만개의 연산을 수행할 수 있다. 
• 그러나 파이썬의 기본 정렬 라이브러리는 n log N의 시간 복잡도를 갖고 있다.
• 그러므로 기본 정렬 라이브러리를 이용하여 이번 문제를 풀 수 없다. 어떻게 풀어야 할까? 

 

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

• O(N)의 시간복잡도를 갖는 정렬 알고리즘
• 배열의 인덱스를 특정 데이터의 값으로 여기는 정렬 방법이다. 
• 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정한다.
• 데이터가 등장한 횟수를 저장한다. 

ex1) [3, 3, 7] 이라는 데이터가 입력된다고 하면, index 3번의 값은 2로 index 7번의 값은 1로 명시되는 것이다.

ex2)

 

 

b) sys.stdin.readline()

• 데이터의 개수가 많은 경우, 파이썬에서는 sys.stdin.readline() 함수를 사용한다. 
• 왜냐면 input() 함수보다 훨씬 빠르기 때문이다. 

 

c) 코드 해설

import sys

n = int(sys.stdin.readline())
array = [0] * 10001 // 주어지는 각 데이터의 범위가 10000이하의 자연수이기 때문

for i in range(n):
    data = int(sys.stdin.readline()) // readline()을 통해 데이터를 입력받는다.
    array[data] += 1 // 해당 데이터의 index값에 등장 횟수를 count 한다.
    
for i in range(10001):
    if array[i] != 0: // 데이터의 등장횟수가 0이 아닌경우  
        for j in range(array[i]): // 해당 데이터의 등장 횟수만큼 출력
            print(i)

- for문은 index 0번부터 읽어나가기 때문에 자연스럽게 오름차순 정렬이 된다.