백준 10989 - 수 정렬하기 3(C언어,C++)(계수 정렬)

 

728x90

백준 10989

 

 

오늘은 백준 10989 수 정렬하기 3문제에 대해 알아보는 시간을 가지겠습니다.

문제를 풀면 분명 맞다고 생각되는데 계속 시간초과나 메모리초과가 나오기에

당황하셨을 겁니다.

오늘은 왜 틀리고 어떻게 해야 하는지 C언어에서 알아보겠습니다.

 

 

문제

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

입력 출력

 

 

해설

 

문제 조건을 보면 N은 1~ 1천만 까지 주어집니다. 그리고 메모리 제한은 8mb입니다.

만약 N만큼 배열을 선언하여 수를 입력받으면 최대 천만 개인데 메모리 8mb면 대략 200만 개 정도의 int형 배열만 만들 수 있습니다. 그렇기에 당연히 메모리 초과가 일어납니다.

 

그럼 어떻게 해야 할까요?

입력으로 주어지는 수의 범위를 살펴봅시다.

10000보다 작거나 같은 자연수, 즉 1~10000입니다.

수의 개수에 비해 너무 작지 않나요?

이걸 이용하는 겁니다.

 

어떻게 이용하느냐? 바로 계수 정렬(카운팅 정렬)을 이용하는 겁니다.

지식 백과를 보면 계수 정렬이란 아래와 같습니다.

 

계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다. 구별되는 키 값들을 소유하는 객체의 수를 계수하고 출력 시퀀
스에 각 키 값의 위치를 결정하기 위한 해당 계수에 전위합을 적용함으로써 동작한다.

 

 

네 뭔 소린지 잘 모르겠습니다.

그래서 문제를 풀면서 쉽게 설명해 드리겠습니다.

 

문제에서 수의 개수 N을 모두 입력받기에는 메모리가 부족하니

일단 입력으로 주어지는 수의 범위인 1~10000, 1만 개의 배열만 만듭니다.

일단 선언된 배열을 a[10000]이라하고

각 부분은 특정 자연수의 개수가 몇 개인지 저장됩니다.

즉 배열의 첫 번째 인덱스인 a [0]에는 자연수 1의 개수

a [1]에는 자연수 2의 개수.... a [9999]에는 자연수 10000의 개수를 의미합니다.

 

 

예시를 그림을 이용해 더 이해하기 쉽게 설명하겠습니다.

예를들어 10개의 정수가 주어지고

그 정수는

5 1 1 2 4 5 3 2 1 1 라고 합시다.

앞에서 입력받으면서 배열에 값을 추가해줍니다.

가장 처음엔 모든 값이 0입니다.

처음 아무것도 없는 상태

 

처음에 값이 5이니 5번째 인덱스에 1을 추가해줍니다.

 

5는 1개가 있다는 것을 의미

 

5번째 인덱스가 1이 되었는데

이는 5가 1개있다는 의미입니다.

 

그 다음 숫자는 1이니 1번째 인덱스에 1을 추가해줍니다.

 

1 1개, 5 1개를 의미

 

1이 1개, 5가 5개 있다는 의미입니다.

이렇게 모든 숫자에 대해 같은 작업을 반복합니다.

아래는 결과 입니다.

 

최종 결과

 

1은 4개, 2는 2개, 3은 1개, 4는 1개, 5는 2개있다는 의미입니다.

이걸 앞에서 부터 출력해주면 됩니다.

그러면 정렬이 되지 않나요?

출력하면 다음과 같습니다.

1 1 1 1 2 2 3 4 5 5

이것이 정답입니다.

이것이 계수 정렬(카운팅 정렬)입니다.

 

 

코드

#include<stdio.h>
int main(void)
{
    int a[10000]={0,},n,b;
    scanf("%d", &n);
    for(int i=0; i<n; i++)
    {
        scanf("%d", &b);
        a[b-1]++;
    }
    for(int i=0; i<10000; i++)
    {
        for(int z=0; z<a[i];z++)
            printf("%d\n",i+1);
    }
}

1을 입력받았을 때 이는 배열의 첫번째 인덱스인 a [0]에 넣어야 하고

다른 숫자들도 -1 한 인덱스에 넣어야 하므로

a[b-1]++를 해주었습니다.

그리고 출력할 때 이중 반복문을 통해

숫자 개수만큼 출력해주었습니다.

 

 

정답!

 

이상 백준 10989 해설을 마치겠습니다.

더 궁금한 점이 있다면 댓글을 남겨주시기 바랍니다.