백준 C++ 10989 수 정렬하기 3 (counting sort, 계수정렬)

이번문제는 굳이굳이 Counting Sort 로 풀어보겠다.

 

카운팅정렬이란? 쉽게말해 배열인덱스를 숫자로 이용하는것.

문제 예시를 보면 숫자1이 두개, 2가 두개, 이런식으로 가다가 6은 없죠?

 

카운팅 정렬은 숫자크기가 정해져있는 문제에서 쓰기좋은데 이유인즉슨

입력 숫자의 최댓값이 10000이라고 문제에서 주어졌으니까

배열크기를 10001로 잡습니다. 그러면 arr[0]~ arr[10000] 까지 생기니깐요?

 

이들을 0으로 초기화 해준다음

 

이런식으로 숫자input이 6이라면

arr[6]값이 1개증가하는형식

 

 

주어진 input 값을 적용해보면

a[0] : 0

a[1] : 2

a[2] : 2

a[3] : 2

a[4] : 1

a[5] : 2

a[6] : 0

a[7] : 1

. 

.

.

이런식이다.

그러면 정렬할 필요가 없어진다. index흘러가는대로 보면 되기 때문에

 

끝.