[정렬 알고리즘] 두 배열의 원소 교체 4. 계수 정렬로 풀어보기

doyeonjeong_·2023년 1월 16일

Algorithm

목록 보기

7/8

📝 계수 정렬 (Counting Sort)

가장 작은 데이터와 큰 데이터를 모두 담을 수 있는 빈 배열을 생성한 후,
각 데이터에 맞는 인덱스에 몇개나 있는지 Count하여 새로운 배열을 만드는 정렬이다.

1️⃣ 순서

1. 가장 작은 데이터와 가장 큰 데이터의 범위를 담을 배열을 생성한다.
2. 배열을 1번 순회하여 아까 만든 배열의 index에 count 한다.

2️⃣ 코드

var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

func countSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0                             // 1. 가장 큰 값을 구한다
    var countArray = [Int](repeating: 0, count: maxValue + 1)   // 2. 가장 큰 값 + 1 크기의 배열을 만든다
    for value in array {
        countArray[value] += 1                                  // 3. 순회하며 해당 값이 있는 index에 count한다
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated() {             // 4. count만큼 index의 값을 append하여 정렬한다
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}

print(countSort(&array))

3️⃣ 정리

안정성 : Stable Sort
- 각 원소끼리 비교하지 않기 때문에 안정성을 가진다.
제자리성 : In-place
- 기존 배열 이외의 메모리를 거의 사용하지 않는다.
시간 복잡도
- 최선 : 𝛰(𝛮) 𝛮이 𝛫보다 클 경우
- 최악 : 𝛰(𝛮 + 𝛫)
장점 : 퀵 정렬의 평균 속도보다 빠를 수 있음. (단, 데이터의 차이가 1,000,000 미만인 경우에 적합)
단점 : 추가적인 메모리가 많이 필요할 수 있다.

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건
1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예
5 3
1 2 5 4 3
5 5 6 6 5

출력 예
26

🌀 풀이

// 계수 정렬
func ascendingCountSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0
    var countArray = [Int](repeating: 0, count: maxValue + 1)
    for value in array {
        countArray[value] += 1
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated() {
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}

func descendingCountSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0
    var countArray = [Int](repeating: 0, count: maxValue + 1)
    for value in array {
        countArray[value] += 1
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated().reversed() {
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}