[백준] 10989번. 수 정렬하기3

https://www.acmicpc.net/problem/10989

내 솔루션 1(실패) – 메모리 부족

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

for i in range(n):
    list.append(int(sys.stdin.readline()))
#↑↑↑↑↑↑↑↑ for문 안에 append 시 메모리 재할당으로 비효율적임

#list.sort() 첫번째 풀이 : 메모리초과

""" 두번째 풀이: 메모리초과
for i in range(n):
    for j in range(i+1,n):
        if list(i) >= list(j):
            temp = list(j)
            list(j) = list(i)
            list(i) = temp

내 솔루션 2 – 계수 정렬

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

arr = (0)*10001 #10,000보다 작거나 같은 자연수 을 미리 할당, 계산 쉽게 +1해줌

for i in range(n):
    a = int(sys.stdin.readline())
    arr(a) += 1
#(0, 2, 2, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0,   

for i in range(10001):
    if arr(i) !
= 0:
        for _ in range(arr(i)):
            print(i)

– 첫 번째 for 문

인쇄(arr) => (0, 2, 2, 2, 1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, …,0)
arr(0),arr(1),arr(2),…, 인덱스를 받는 것으로 생각하세요!

입력 a가 (2,2,1)이면 2가 두 번 나타남 => arr(2) =2, 세 번 나타나면 arr(2) =3

– 두 번째 for 문

외부 for 문에서 arr(i) !
= 0이면 i를 인쇄합니다.

문제를 해결하다

• 백준 #2750, #2751 처럼 풀면 메모리부족!
  
• 웹 검색 시 계수정렬을 사용하므로 메모리를 효율적으로 할당해야 합니다.
  
• for 문 추가 시 메모리 재할당으로 인해 비효율적임

정렬 카운팅

• 배열의 인덱스를 특정 데이터의 값으로 취급하는 정렬 방식
• 데이터 범위 (예)arr=(0)*10001을 포함하도록 배열의 크기가 조정됩니다.
  
• 데이터가 몇 번이나 나타나는지 계산 (ex)arr(i) += 1
• 예) (3,3,7) =? 3이 두 번 나타남: 3의 인덱스는 2, 7은 한 번 나타남: 7의 인덱스는 1