B)10989

수 정렬하기3

문제

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

입력

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

출력

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

메모리 제한, 수의 개수, 수의 범위에 주목을 해야겠다.
보지도 않고 수 정렬하기2 코드 복붙하다가 깨달은,,
수 정렬하기1,2 보다 시간 제한이 늘었지만, 수의 개수 최댓값이 상당하다,,

계수정렬!!!!

필자는 수차례 시도한 끝에 얻은 결과,,
이전 포스팅에서 다룬 계수정렬이, 정렬할 수의 최댓값이 작다면, 굉장히 효율적인 방법이란걸 알았기 때문에, 써보면 어떨까?
수의 개수는 10,000,000이하, 수는 10,000보다 작거나 같은 자연수 라는 조건을 보면, 수의 크기가 개수보다 현저히 작기 때문에, 매우 효율적일거라고 판단된다.

unsorted = [0] * 10001

문제에서, 10000보다 작은 수라고 던져줬으니, 편의상 10001개의 배열을 만들었다.

for i in range(N):
    n = int(sys.stdin.readline())
    unsorted[n] = unsorted[n]+1

사용자 입력을 받고, 0으로 초기화된 배열에서 입력에 해당되는 인덱스의 값을 1 늘려준다.

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

저장된 배열을 탐색하며, 0이아닌 배열의 인덱스를 출력해주면, 정렬된 값을 얻을 수 있다. 코드를 병합해보면,

import sys
#input() 의 속도가 느리기 때문에, sys.stdin.readline()을 사용한다.
N = int(input())

unsorted = [0] * 10001

for i in range(N):
    n = int(sys.stdin.readline())
    unsorted[n] = unsorted[n]+1

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

사실 처음엔 input()을 사용했는데, 이 함수가 생각보다 효율적이지않은 입력 함수라는걸 이번에 알게 되었고 그래서 사용하게 된 것이
sys 라이브러리의 sys.stdin.readline()이라는 함수다. 많은 양의 입력을 받아들이는데에, 효율적인 함수라는걸 배우게 되었다.

정리

사실 알고리즘 문제를 많이 풀어보지 않아서, 공간,시간을 효율적으로 다루는데에 어려움을 많이 겪고있다.
그런 부분에서 이 수 정렬하기 1,2,3은 비슷한 유형이면서 공간,시간 활용을 어떻게 해야할지 갈피를 잡아주는 좋은 문제라는 생각이 들었다.
더 많은 알고리즘을 공부하며, 좋은 코드를 만들어내야겠다.