[BOJ/백준 - 10989] 수 정렬하기 3

문제 출처: https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

---

 

일단 

수 정렬하기 1,

수 정렬하기 2는 풀었을 것이다

 

근데 해당 문제인 수 정렬하기 3은 문제 밑의 코멘트에

'수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.'

라고 적혀있고 작성 당시 기준 정답 비율이 22~23%이다

 

이걸 보면 따로 알고있는 방법이 없다면 카운팅 정렬을 써야할것을 알 수 있다

근데 카운팅 정렬을 아는가?

 

알면 좋은데 난 몰랐음

그래서 카운팅 정렬이 뭔지 찾아봄

 

어느 글을 읽었더니 '입력값이 정수가 보장되어 있다면 수를 비교하지 않고 하는 정렬' 이런식으로 적혀있었음

수를 비교하지 않음 + '카운팅' 정렬임 -> 아하

 

(입력값+1) 크기의 배열을 만든다음 

배열[입력값]++;

입력이 끝나면 배열을 차례대로 돌면서 카운팅된 만큼 인덱스값을 출력함

 

나는 모두 출력되도 배열의 끝까지 보내는게 싫어서 값을 하나씩 줄일때마다 N도 줄여서

N값이 0이되면 바로 출력하게 해놓았음

 

오늘도 하나 건져간다