[BOJ][Python][10989] 카운팅 정렬

[문제 및 출처]

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

10989번: 수 정렬하기 3

[어떻게 풀까?]

이 문제는 카운팅 정렬을 이용해서 풀라는 설명에 따라서 카운팅 정렬이 무엇인지 찾아보았다. 

간단하게 생각해서 list를 만들어서 그 list의 인덱스에 해당하는 값에 +1을 해주면 된다.

예를 들어 list가 

array = [1, 1, 3, 7, 10] 

이라고 한다면

1	2	3	4	5	6	7	8	9	10
2	0	1	0	0	0	1	0	0	1

이런식으로 작동하게 된다. 그래서 간단하게 코드를 작성해 보았다.

#정렬하는 수의 범위가 작다면 카운팅 정렬을 사용!

n = int(input())
array = []

for i in range(n):
    new = int(input())
    array.append(new)

#0부터 가장 큰 수까지, 인덱싱하기 편하게
sorting_array = [0] * (max(array)+1)

#값에 맞는 인덱스에 더해진 상태
for i in range(len(array)):
    sorting_array[array[i]] += 1 #n번째 인덱스 +1

#출력
index = 0
for i in sorting_array:
    if i == 0:
        index += 1
        continue
    for j in range(i):
        print(index)
        
    index += 1

처음엔 이런식으로 구성해보았다. 하지만 메모리 초과라는 형태의 문제점이 발생하였고 나는 이를 해결하기 위해 이것 저것 뒤져보았다. 처음엔 딕셔너리를 사용해볼까 했지만 본래의 취지의 맞지 않는 것 같아서 접었다.

다음으로 요즘 배우고 있는 C++로도 해결해보려고 하였다. C++의 장점은 빠른 것이니까. 

#include <iostream>
using namespace std;

int main(void)
{   
    int n;
    cin >> n;

    int array[n+1]; //크기가 n+1인 배열 새성
    int counting_array[10001] = {0, };
    //정렬할 수들 구하기
    for(int i=0; i<n; i++)
    {   int temp;
        cin >> temp;
        array[i] = temp;
    }

    //counting 하기
    for(int i=0; i<sizeof(array)/sizeof(int); i++)
    {
        counting_array[array[i]] += 1;
    }

    //출력하기
    for(int i=0; i<sizeof(counting_array)/4; i++)
    {
        for(int j=0; j<counting_array[i]; j++)
            cout<<i<<"\n";
    }
}

하지만 결국 메모리 초과라는 같은 문제점이 발생하였고, 언어가 Python이라서 못 푼것이 아니라 시간 복잡도나 메모리를 불필요하게 쓴다는 점이 내 문제점이라는 것을 깨달았다. 

 

결국 해결 법을 찾아냈다.

1. 수의 범위가 10000이하라는 점

2. 그리고 굳이 list를 2개씩 만들 필요가 없다는 점

이를 따라서 코드를 작성하게 된다면 다음과 같다.

import sys

n = int(sys.stdin.readline())
array = [0] * 10001
for i in range(n):
    temp =int(sys.stdin.readline())
    array[temp] += 1

for i in range(len(array)):
    if array[i] == 0:
        continue
    for j in range(array[i]):
        sys.stdout.write("%d\n"%i)

중간 과정에서 sys.stdin, sys.stdout등을 열심히 시도한 흔적들이 보인다.

[코드 설명]

일단 0으로 구성된 배열 10001개를 만든다. 인덱싱하기 편하게 1개 더 만들어 인덱스와 실제수가 대응되게 만들어 주었다.

다음으로 배열에 인덱스에 맞는 값에 바로 +=1 을 해준다 이렇게 하면 굳이 list를 하나 더 만들지 않아도 된다.

그렇게 해서 출력해주면 된다.