[정렬/counting sort] BAEKJOON ' 10989'번 '수 정렬하기3 '문제 (C++/python)

문제 : www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

 

• 문제 해결 아이디어

    1.  배열에 모두 저장하여 stl을 활용하여 해결하면 간단한 문제이지만, 최대 1000만개의 데이터가 주어지기에 stl을 이용하지않는다.

   

    2.  입력받은 값들을 모두 저장하지않고 해결하기 위해 counting sort를 이용한다.

 

        ( counting sort에 대한 내용은 knowable.tistory.com/17에서 확인할 수 있다. )

 

 

• python

import sys

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

for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1

for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

처음 n이 최대 1000만까지 입력이 될 수 있기 때문에, 값을 빨리 읽기위해 (시간초과 방지) readline을 사용한다.

 

 

 

• c++

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

unsigned int num,i;

int main(){
    
    int arr[10001]={0,};
    
    scanf("%u",&num);
    
    for(i=1 ; i< num+1 ; i++){
        int tmp;
        scanf("%d",&tmp);
        arr[tmp]++;
    }
    
    for(int j=1; j<10001; j++){
        if(arr[j] != 0){
            for(int k=0 ; k< arr[j] ; k++)
                printf("%d\n",j);
        }
    }
    
    return 0;
}

처음 n이 최대 1000만까지 입력이 될 수 있기 때문에, 이를 소화하기 위해, unsigned int를 전역변수로 선언해준다.

(지역변수는 스택에 메모리 공간을 잡기 때문에, 큰 배열을 선언하게 되면 해당 프로세스의 스택사이즈를 초과하게된다.

전역변수는 힙 공간에 메모리 공간을 잡기 때문에, 이와같은 제한에서 자유롭다.)