백준 10989번 파이썬 문제풀이(정렬 - 수 정렬하기3)

-> 다음 문제에서 체크해야 할점은 자연수, 메모리 제한 8MB 이다.

 

import sys

n = int(input())
array = [0] * 10001

for i in range(n):
    n = int(sys.stdin.readline())
    array[n] += 1  # 각 데이터에 해당하는 인덱스 값 증가(== 인덱스가 해당 숫자 이고 들어간 값이 해당숫자의 개수 ex) array[2] = 3 이면 숫자 2가 3번 있다는 뜻)

for i in range(len(array)): #array의 길이만큼
    for j in range(array[i]): #해당 숫자(i)의 개수만큼
        sys.stdout.write(str(i) + "\n") #출력

-> 파이썬의 기본 내장함수를 사용하게 될 경우 메모리 초과가 발생한다. 따라서 다른방법을 사용해야하는데 위의 정렬은 계수정렬과 비슷하다.

 

계수정렬은 해당 수가 음수가 아닐 경우 사용가능한 정렬방식인데 , 배열의 인덱스를 숫자로 배열의 인덱스에 저장되어 있는 값을 해당 숫자의 개수로 사용하여 정렬 하는 방식이다. 

 

위의 예에서 입력받은 n값을 리스트의 인덱스값으로 활용하고 있으며 n값이 한번 등장할때 마다 해당 인덱스에 +1 씩 해준다. 즉 2을 2번 입력받았다면 array[2] = 2 가 저장이 될 것이다.

 

그 후 출력할때는 해당 리스트의 길이만큼 반복문을 돌고 각각의 인덱스에 접근하여 저장되어 있는 값이 0보다 크다면 그 저장되어있는 값만큼 출력하면 된다.