백준 파이썬 10989번: 수 정렬하기 3

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

문제 유형: 정렬

 

# Solution 1 - 런타임 에러 (IndexError)

import sys
 
n = int(sys.stdin.readline())
count = [0] * 10000

for i in range(n):
    count[int(sys.stdin.readline())] += 1
    
for i in range(10001):
    if count[i] != 0:
        print('%d\n'%i * count[i], end = '')

 

# Solution 2

import sys

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

for i in range(n):
    count[int(sys.stdin.readline())] += 1
    
for i in range(10001):
    if count[i] != 0:
        print('%s\n'%i * count[i], end = '')

메모리 제한 때문에 기존에 풀었던 방식(모든 수를 입력받고 정렬하는 방법)으로는 도무지 풀리지 않았다. 전혀 다른 접근 방식이 필요하다는 걸 깨닫고 위의 방법을 시도했다.

 

 

위 방법은 계수 정렬(Counting Sort) 알고리즘이라고도 하며 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법이다.

 

1. 미리 0이 10001개 있는 리스트를 만들어준다. (딱 10000개가 들어있는 리스트를 만들었더니 런타임 에러가 났다! 배열의 크기는 반드시 데이터의 범위를 포함할 수 있도록 설정할 것)

2. 입력받은 숫자를 리스트의 인덱스로 사용, 해당 숫자의 위치에 1씩 더해준다. 같은 숫자가 두 번 입력되면 그 인덱스의 값은 2가 된다.

3. 마지막 for문에서 0으로 남아있는 아이템은 제외시키고 값이 있는 숫자들만 출력한다.