[정렬 알고리즘] 두 배열의 원소 교체 1. 선택 정렬로 풀어보기

알고리즘 스터디

이코테 책에서는 python의 sort함수를 사용하여 비교적 문제 난이도가 낮았다.
따라서 조금 더 알찬 스터디를 위해 선택, 삽입, 퀵, 계수 정렬을 이용하여 문제를 풀어보기로 했다.
( 분량 조절 실패로 인해 글을 4개로 나누게 되었다. )

📝 선택 정렬 (Selection Sort)

매번 가장 작은 원소를 찾아 순차적으로 정렬하는 방법이다.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 배열을 순회하여 가장 작은 데이터를 선택한다. data[3] = 0
2. 맨 앞에 있는 요소와 바꾼다.
	data[0] = 7 <-> data[3] 0
	data = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
3. 이제 0번째 index의 정렬을 완료했으니 1번째 index의 값도 위의 방식으로 정렬한다.
4. 위 과정을 반복하여 배열 끝까지 정렬한다.

2️⃣ 코드

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

for i in 0 ..< array.count {            // 1. 왼쪽부터
    var minIdx = i                      // 2. 가장 작은 원소 찾기
    for j in i + 1 ..< array.count {    // 3. 현재 위치 + 1부터 끝까지
        if array[minIdx] > array[j] {   // 4. 더 작은 값이 있다면
            minIdx = j                  // 5. 더 작은 인덱스로 초기화
        }
        array.swapAt(i, minIdx)         // 6. 현재 위치와 더 작은 값의 위치 Swap
    }
}

3️⃣ 정리

• 안정성 : Unstable Sort
  - 동일한 값을 가지는 원소의 본래 순서를 보장하지 않는다.
• 제자리성 : In-place
  - 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도 : 𝛰(𝛮 ²)
  - 방법이나 코드는 단순하지만 2중 반복문으로 인해 비효율적인 편이다.

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

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

// 공통 input
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, k) = (input[0], input[1])
var a = readLine()!.split(separator: " ").map { Int(String($0))! }
var b = readLine()!.split(separator: " ").map { Int(String($0))! }

// 기본 라이브러리 사용
a.sort()
b.sort(by: >)

for i in 0 ..< k {
    if a[i] < b[i] {
        a[i] = b[i]
        b[i] = a[i]
    } else {
        break
    }
}
print(a.reduce(0, +))

그렇다. 책에서는 기본 라이브만 이용했기 때문에
정렬 챕터에 있는 모든 문제 난이도가 낮았다...
각 정렬로 풀어보기 전까지 이게 이렇게 오래 걸릴 줄 몰랐다...

// k번 바꾸기 연산 - 문제 풀이 로직
func exchange(_ a: inout [Int], _ b: inout [Int], _ k: Int) -> [Int] {
    for i in 0 ..< k {
        if a[i] < b[i] {
            a[i] = b[i]
            b[i] = a[i]
        } else {
            break
        }
    }
    return a
}

// 선택 정렬
func selectionSort(_ array: inout [Int], _ oper: String) {
    if (oper == "<") || (oper == "") {
        for i in 0..<array.count {
            var minIndex = i
            for j in i+1..<array.count {
                if array[j] < array[minIndex] {
                    minIndex = j
                }
            }
            if i != minIndex {
                array.swapAt(i, minIndex)
            }
        }
    } else if oper == ">" {
        for i in 0..<array.count {
            var minIndex = i
            for j in i+1..<array.count {
                if array[j] > array[minIndex] {
                    minIndex = j
                }
            }
            if i != minIndex {
                array.swapAt(i, minIndex)
            }
        }
    }
}

selectionSort(&a, "<")
selectionSort(&b, ">")
print("답 : \(exchange(&a, &b, k).reduce(0, +))")

오름차순과 내림차순을 구분해주기 위해 "<", ">"를 사용했다.
바로 이어서 삽입 정렬로 넘어가보자...!