[백준] 10989 - 수 정렬하기 3

Silver  V 

 

 

문제 ( www.acmicpc.net/problem/10989 )

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

 

입력

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

 

출력

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

 

예제

input	output
10 5 2 3 1 4 2 3 6 1 7	1 1 2 2 3 3 4 5 5 7

 

나의 코드

간단하게 sorted와 lamda식을 써서 한 번 돌려보았다.

import sys

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

numbers = [_ for _ in range(n)]
for i in range(n):
    numbers[i] = int(sys.stdin.readline())

numbers = sorted(numbers, key=lambda numbers: numbers)

for i in range(n):
    print(numbers[i])

첫 시도에서 메모리 초과가 발생했다. 메모리 제한이 8MB라서 여태 사용해온 정렬로는 통과할 수 없는 것 같다.

 

 

문제 아래쪽을 보니 카운팅 정렬을 사용하라고 적혀 있었다.

 

www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

위 사이트를 통해 counting sort 알고리즘을 이해하고 다시 풀어보았다.

import sys

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

a = [0]*n
b = [0]*(n+1)

counting = [0]*10001

for i in range(n):
    a[i] = int(sys.stdin.readline())
    counting[a[i]] += 1 # count

for i in range(1, 10001): # 누적 합
    counting[i] += counting[i - 1]

for i in range(n - 1, -1, -1):
    b[counting[a[i]]] = a[i]
    counting[a[i]] -= 1


for i in range(1, n+1):
    print(b[i])

카운팅 정렬을 사용했지만 또 메모리 초과가 발생했다.

 

검색을 해보니 사람들은 카운팅 정렬을 그대로 사용하지만은 않았다. count한다는 개념은 그대로 적용했지만, 누적 합을 사용하지 않고 바로 출력을 하게 한 것 같았다.

 

이해한 대로 다시 짜보았다.

import sys

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

counting = [0]*10001

for i in range(n):
    input = int(sys.stdin.readline())
    counting[input] += 1 # count

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

counting 배열에서 0이 아닌 값을 가지는 index를 활용해 출력하는 방법이다.

드디어 맞았습니다!! 가 떴다.