[백준 #10989] 수 정렬하기3(카운팅 정렬) - 파이썬(python)

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

처음엔 똑같은 문제가 계속 나와서 왜 그런거지 생각하면서 전에 했던 것 대로 똑같이 했더니

계속 메모리 초과가 났다..

 

아마 input,count,ouput array를 다 따로 만들어서 그런듯,,

카운팅 정렬을 이해하는데도 엄청나게 많은 시간이 걸렸는데,

그것을 나만의 코드로 짜려고 하니까 머리에 쥐 날 뻔 했다.

 

import sys 
N = int(input()) 
check_list = [0] * 10001
for i in range(N): 
    input_num = int(sys.stdin.readline()) 
    check_list[input_num] = check_list[input_num] + 1 
for i in range(10001): 
    if check_list[i] != 0: 
        for j in range(check_list[i]): 
            print(i)

결국에는 위와 같이 코드를 짰는데 아직도 완벽하게 이해했다고 할 수 없을 것 같다.

 

내가 이해한바로는

input array에 있는 값을 주소로 하는 count 배열에 수를 카운팅 해서 역순으로 배열을 다시 정렬하는 것 같다.

 

예를들어,

input = [1,2,4,2,3,7] 라는 배열이 있다고 하면

count 배열은 input의 max 값인 count[7]까지 있고 사전에 0으로 다 채워넣은 배열이 된다.

Input 배열에 2라는 값이 있을 경우 count[2] 값이 1씩 올라간다고 생각하면 되고,

카운팅이 모두 끝나면 count 값을 누적해서 배열을 갱신한다.

카운팅이 count=[0,1,2,1,1,0,0,1] 이었다면

count = [0,1,3,4,5,5,5,6]으로 누적배열함.

count[input 값]이 시작하는 자리가 count[input 값]-1의 값인 것이다.

ex) count[7]=6-1=5

--> input값의 7은 정렬 된 후 input[5]의 자리부터 1만큼 차지하는게 되는 셈이다.

 

안 쓰고 머리로만 이해하려다가 그림 그려서 한 번 보니 이해가 잘 되었다.

새로운 것을 하나 배워서 기분이 매우 좋음