Swift로 LetCode-Squares of a Sorted Arry 설명

원래 문제가 영어였기 때문에 대체 번역한 내용을 기재했다.

도대체 하나의 예일 뿐이고 다른 방법도 존재한다고 대답했다.

개막사

스위프트로 Sort 알고리즘을 써본 적이 없는 사람에게는 좋은 학습 문제다.

문제.

문제.
난이도
Squares of a Sorted Array
easy

整数の配列 nums が小さい順にソートされています。
各数値を2乗した配列を小さい順にソートして返します。

를 보충으로 다음과 같은 실제 테스트 용례를 제공하였다.

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

테스트 용례의 계산 과정은 다음과 같다.

원시치→[-4,-1,0310]

제곱→[16,1,09100]

순서→[0,1,916100]

하나의 점으로, 만약 수조에 음수가 있다면, 제곱이 되면, 이 값은 플러스로 반전된다.이때 처음에는 작은 순서로 정렬된 순서가 바뀌기 때문에 다시 정렬해야 한다.

답안

Swift API 사용 방법

Sort 알고리즘을 사용하는 방법

라는 두 가지 소개를 했다.

1. Swift API 사용 방법

func sortedSquares(_ A: [Int]) -> [Int] {
    return A.map { $0 * $0 }.sorted()
}

Swift에는 sorted 방법이 있습니다.sorted 메서드 내부에는 여러 개의 Sort 알고리즘이 조합되어 있습니다.따라서 스스로 Sort 알고리즘을 설치하기보다는 이를 사용하는 것이 더 빠르다.
(참조: Swift 정렬 방법
하지만 이번에는 알고리즘을 사용하는 방법을 봐야 한다.

2. Sort 알고리즘을 사용하는 방법

정렬 알고리즘이 몇 개 있는데 이번에는 두 가지를 소개합니다.

① Bubble Sort(거품 정렬)

인접 요소의 값을 비교하고 조건에 따라 교환하는 알고리즘.

(참조: 간단한 거품 정렬 기준
그럼 실제 코드를 봅시다.

func sortedSquares(_ A: [Int]) -> [Int] {
    // ① ２乗した配列を作る
    var result = [Int]()
    for n in A {
        result.append(n*n)
    }
    
    // ② ソートしていく
    var isSwapped = true
    while isSwapped {
        // 一度でも値の交換をした場合は、再度比較をし直すためのフラグ
        isSwapped = false
        
        // 最初から数字を比較していく
        // 中の計算で'i-1'をしても問題ないように'０'ではなく'1'から始まっている
        for i in 1..<result.count {
            // 隣り合う数字の比較
            guard result[i] < result[i-1] else { continue }
            // 該当する場合は'swapAt'で値を交換する
            result.swapAt(i, i-1)
            isSwapped = true
        }
    }
    return result
}

도 재기 함수를 사용하는 문법이 있는데 이번에는 while와フラグ로 쓴다.
이번 소개는 버블 소트가 평균적으로 비교되기 때문에 계산량이 매우 많고 시간이 오래 걸리기 때문이다.이 문제에 사용하면 시간 초과가 유감입니다.
그럼 이보다 빠른 Sort 알고리즘을 살펴봅시다.

② Merge Sort(병합 정렬)

정렬되지 않은 목록을 두 개의 목록으로 나누어 각각 정렬한 다음 그것들을 하나의 (통합) 알고리즘으로 통합시킨다.

(참조: 소스 코드 탐험대, 총 1870개, 알고리즘과 데이터 구조, 총 18.6개, 통합 정렬
그럼 실제 코드를 봅시다.

func sortedSquares(_ A: [Int]) -> [Int] {
    // ① ２乗した配列を作る
    var squaredNums = [Int]()
    for n in A {
        squaredNums.append(n*n)
    }
    
    // ② ソートしていく　&　③ 合成する 
    return mergeSort(squaredNums)
}

func mergeSort(_ lists: [Int]) -> [Int] {
    guard 1 < lists.count else { return lists }
    
    // ②-1 配列を２つに分割
    let count = lists.count
    let left = Array(lists[..<Int(count/2)])
    
    // ②-2 分割した個々の配列をソートし続ける
    let right = Array(lists[count/2...count-1])
    return merge(left: mergeSort(left), right: mergeSort(right))
}

func merge(left: [Int], right: [Int]) -> [Int] {
    var left = left, right = right, result = [Int]()
    
    // ③-1 ２つの配列から最初の値を見て、小さい値から順にリストに追加していくことで、２つの配列を合成していく
    while 0 < left.count && 0 < right.count {
        // `removeFirst`で追加した方の先頭の値を除外していく
        if left[0] <= right[0] {
            result.append(left.removeFirst())
        } else {
            result.append(right.removeFirst())
        }
    }
    
    // ③-2 `while`ではいずれかが'０'になった時に処理が終わってしまうので、最後の値を配列に追加する
    result.append(contentsOf: left)
    result.append(contentsOf: right)
    
    return result
}

메르지소트에는 각각'sort할 함수'와'merge할 함수'가 준비돼 있다.언뜻 보기에는 코드량이 많지만 버블 소트와 달리 각 배열을 보면서 비교값의 계산량을 줄인다.
Sort 두 개를 소개했고 알고리즘도 몇 개 더 있으니 관심 있는 분들은 조사해 보세요.

실행 결과

Kind
Runtime
Memory
sorted()
380ms~
16MB 정도
Bubble Sort
Time Limit Exceeded
-
Merge Sort
740ms~
16MB 정도

인용하다

소스 코드 탐험대, 총 1870개, 알고리즘과 데이터 구조, 총 18.6개, 기포 정렬

소스 코드 탐험대, 총 1870개, 알고리즘과 데이터 구조, 총 18.6개, 통합 정렬

swift-algorithm-club Bubble Sort

swift-algorithm-club Merge Sort

Merge Sort In Swift