계수 정렬(Counting Sort)

Swift에서 Counting Sort(계수 정렬)을 사용하는 방법

Counting Sort(계수 정렬)란 주어진 수를 오름차순하는 정렬이다.

정렬에 필요한 시간 복잡도는 O(n + k)로 적은 숫자 같은 경우에는 속도가 빠르다는 장점이 있지만 수백만까지 입력되는 경우면 매우 느릴 수 있다는 단점이 있다.

1. 입력받은 배열(inputArray)을 [3, 1, 4, 0, 2, 1, 3, 4]라고 가정하면 가장 작은 수는 0, 가장 큰 수는 4이기 때문에 5칸의 배열을 만들어 준다. 여기서의 시간복잡도는 O(n)이다.

var array = [Int](repeating: 0, count: 5)

2. 각 숫자가 몇 개씩 있는지 세어주기 위해 Count Array를 만들어 주고 0으로 초기화를 해준다.

var countArray = [Int](repeating: 0, count: 5)
countArray: [0, 0, 0, 0, 0]

3. 위에 만들어진 배열(Array)을 순회하면서 Count Array에 각 index번호에 맞게 +1씩 해준다.

for i in inputArray {
	countArray[i] += 1
}
countArray: [1, 2, 1, 2, 2]

4. 각 수가 몇 번째 index에서 끝나는지 알기 위해서 Count Array의 각 수를 누적합을 해준다.

for i in 0..<countArray.count {
	let sum = countArray[i] + countArray[i - 1]
    sumArray.append(sum)
}
countArray: [1, 3, 4, 6, 8]

5. Counting을 통해서 index를 만들었기 때문에 모든 element에서 offset을 -1로 맞춰준다. 여기까지의 시간 복잡도는 O(k)이다.
6. 최종적으로 sortedArray는 countArray에서 1을 빼준값을 인덱스로 활용하여 inputArray의 값을 sortedArray의 인덱스로 찾아가서 값을 넣어준다.
   이렇게 하면 각 숫자가 오름차순으로 정렬된 결과를 볼 수 있다. 여기서의 시간복잡도는 O(n)이어서 최종적으로 O(n+k)라는 시간복잡도가 나온다.

var sortedArray = [Int](repeating: 0, count: array.count)
for i in array {
  ->  countArray[i] -= 1 
  ->  sortedArray[countArray[i]] = i
}

1. countArray: [1, 3, 4, 5, 8]
   -> inputArray의 첫번째 값이 3이고 3번째 인덱스에 -1을 해준다.
   -> sortedArray에 countArray의 3번 인덱스 값인 5번째 인덱스값에 3을 넣어준다.
   sortedArray: [0, 0, 0, 0, 0, 3, 0, 0]
2. countArray: [1, 2, 4, 5, 8]
   -> inputArray의 두번째 값이 1이고 1번째 인덱스에 -1을 해준다.
   -> sortedArray에 countArray의 1번 인덱스 값인 2번째 인덱스값에 1을 넣어준다.
   sortedArray: [0, 0, 1, 0, 0, 3, 0, 0]
3. countArray: [1, 2, 4, 5, 7]
   -> InputArray의 세번째 값이 4이고 4번째 인덱스에 -1을 해준다.
   -> sortedArray에 countArray의 4번 인덱스 값인 7번째 인덱스값에 4을 넣어준다.
   sortedArray: [0, 0, 1, 0, 0, 3, 0, 4]
   ...
   이런식으로 for문을 다 돌면
   sortedArray: [0, 1, 1, 2, 3, 3, 4, 4]처럼 값이 나오게 된다.

---

이를 활용하여 백준문제를 풀어봤는데 시간초과가 나서 해결을 못하고 있다....
백준 10989

import Foundation

let n = Int(readLine()!)!

var array: [Int] = []

for _ in 1...n {
   array.append(Int(readLine()!)!)
}

let maxValue = array.max()!

var countArray = [Int](repeating: 0, count: maxValue + 1)

for i in array {
   countArray[i] += 1
}

for i in 1..<countArray.count {
   let sum = countArray[i] + countArray[i - 1]
   countArray[i] = sum
}

var sortedArray = [Int](repeating: 0, count: array.count)

for i in array {
   countArray[i] -= 1
   sortedArray[countArray[i]] = i
}

print(sortedArray)

참고
https://www.youtube.com/watch?v=Urmb0FpW6Hk&t=297s
https://joycestudios.tistory.com/62