[백준 10989] 수 정렬하기3 (브론즈1)

문제

 

접근방법

제일 처음 이 문제를 보고 수 정렬하기1이랑 똑같이 제출했는데 역시나 틀렸다... 이 문제를 풀기 위해서는 문제를 자세히 읽어봐야 한다.

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

이 부분과 메모리 제한이 8MB인것이 핵심이다.(사실 몰라서 구글링하다가 알게됨 ㅋ)

수 정렬하기1 코드랑 똑같이 제출했지만 틀린이유는 우선 메모리 크기부터가 이 문제가 훨씬 적다. 그래서 오답이었다.

이 문제는 카운팅정렬을 써야한다

왜 카운팅 정렬을 쓰는지는 밑에서 설명...

 

 

개념

카운팅 정렬(Counting Sort)이란

입력의 개수가 아닌 크기의 영향을 받는 정렬 알고리즘이다.

https://bowbowbow.tistory.com/8 

Counting Sort : 계수 정렬

개념이 이해가 안갔는데 이분의 설명을 참고했다. 그림 하나하나 그려가면서 설명해주신다 아주 굿이다

이 정렬은 해당 데이터의 개수가 몇개인지만 세면 된다.

https://gusdnd852.tistory.com/130

정렬 (12) - 계수 정렬 (Counting Sort)

이 분의 설명도 참고했다!

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 10000

int main() {
	
	int counting[SIZE + 1];
	for (int i = 0; i < SIZE + 1; i++) {
		counting[i] = 0; 
	}
	//카운팅 배열 선언,초기화

	int n, num;
	scanf("%d", &n);


	for (int i = 0; i < n; i++) {
		scanf("%d", &num); //정렬할 숫자들을 배열에 입력
		counting[num]++;
	}

	for (int i = 0; i < SIZE + 1; i++) {
		for (int j = 0; j < counting[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}

1.

입력될 수의 범위는 최대 10,000이라고 문제에서 미리 말했기 때문에 최댓값인 10,000 + 1만큼의 카운팅 배열을 선언해준다.(최대값이 얼마인지 알고 있어야한다)

 

2.

입력을 받으면서 숫자들을 카운팅배열에 넣는다. 최대 인덱스는 10,000이라서 어떤수를 넣어도 들어간다. 이미 크기를 10,000+1로 선언했기 때문에

예를 들어 내가 10개의 숫자를 입력할거고 " 5 2 3 1 4 2 3 5 1 7 "이렇게 입력한다고 하자

5
2
3
1
4
2
3
5
1
7

그러면 카운팅배열은 이렇게 만들어진다.

(배열의 인덱스번호) 0	1	2	3	4	5	6	7	8	9
0	2	2	2	1	2	0	1	0	0

 

for (int i = 0; i < n; i++) {
		scanf("%d", &num);
		counting[num]++;
	}

내가 입력하려는 처음 숫자부터 각각 숫자에 해당하는 배열의 인덱스 값을 증가시키는 것이 핵심이다 이 부분이 이해가 안가서 진짜 엄청 애먹었다. 다시말해 저기서는 5가 2번 입력되니까 카운팅배열에 5에 해당하는 5인덱스에 값을 2번 증가시킨다는 것이다. 그래서 표에 나온것처럼 인덱스 5에는 숫자2가 들어간다. 내가 입력하려는 값이 100이 있으면 카운팅배열의 인덱스 100까지 가서 거기에 값이 몇번 나왔는지 기록하는것이다. 

결과적으로 각각 숫자가 나온 개수만큼 배열들이 값을 가지게 된다!!!!! 그래서 정렬할 그 값의 최대값이 중요하다 

1 2 5 3 4 100 0 8 이렇게 정렬을 한다면 100 숫자 하나때문에 배열의 0부터 100까지 모든값을 입력해야하니까.

 

 

3.

for (int i = 0; i < SIZE + 1; i++) {
		for (int j = 0; j < counting[i]; j++) {
			printf("%d\n", i);
		}
	}

마지막으로 정렬된 숫자들을 출력하면된다.

카운팅배열의 크기는 0부터 10001까지이다. 이 카운팅배열을 반복문을 통해 돌려준다.

인덱스 i를 각각 counting[i]회 출력하면 끝! 

예를 들어 인덱스 i=1에서는 그 배열의 값이 2이다. 그러니까 인덱스 1를 각각 counting[1](이 배열의 값은2니까) 2회 출력한다는 뜻이다. 

i=1일때 j<2니까 0<2, 1<2 총 2번 출력한다는 뜻,

printf("%d\n', i) (-> "i"는 인덱스임) 2번출력을 하는데 어떤 숫자를 출력하냐면 인덱스의 번호인 1를 2번 출력한다는 뜻이다

 

 

출처

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

10989번: 수 정렬하기 3