CS ﹒ Algorithm/Baekjoon
2022. 7. 19.
JAVA 백준 문제풀이 (23) 10989 : 수 정렬하기3
백준에서는 계수 정렬(Counting sort)로 풀 것을 권장하고 있으나, 궁금해서 각각 실험해본 결과 퀵정렬과 병합정렬로도 3초 내에 통과할 수 있었다. 빠르기는 계수 정렬이 가장 빠르기는 했다. 차례로 계수 정렬, 퀵 정렬, 병합 정렬(내장)이다. 근데 계수 정렬에는 치명적인 단점이 있어서 알고리즘 풀이용으로는 거의 쓰이지 않는다고 한다. 일단 계수 정렬이 무엇인지 간단하게 알아보자. 글보다 코드와 그림이 더 와닿을 것이다. 정렬할 배열의 최대값을 구한 뒤 최대값 만큼의 배열을 만든다. ( array[max+1] ) 그리고 정렬할 배열을 체크하며 값을 생성한 배열의 인덱스에 대입해서 카운팅한다. ex) { 2, 1, 3, 1, 2, 2 }라는 배열을 couting sort를 이용해 체크한다면 2가 ..
