[Swift 알고리즘] PermMissingElem - Codility

PermMissingElem coding task - Learn to Code - Codility

---

요약

80 → 100

처음에 문제 이해가 부족해서, 정답 제출 후 헤매다가 빠진 케이스를 찾아냈다.

그러나 이렇게 푸는 문제가 아니었다 ㅋㅋ

더 나은 풀이를 확인하면 아주 수학적으로 멋지게 해결하더라.

지금까지 코딜리티 문제들은 수학적으로 접근하는 것을 선호하는 듯하다.

마치 비문학을 읽고, 의사 코드를 적어서 제출하는 듯한 프로그래머스와는 다른 부분이다.

나의 풀이

import Foundation
import Glibc

// 문제가 헷갈리는데, [1..(N+1)] 범위의 정수형 원소가 담긴 배열에서, 사라진 하나의 원소를 찾는 것 같다. /
// 범위가 다소 애매하다. [1..(N+1)]이면 [1..<N+1]을 의미하는 것인가? 그러면 사라진 원소가 없을텐데...

// 일단 가정대로 풀이하자.
// let size = A.count
// var checkArr: Array(repeating: false, count: size + 1)
// checkArr[0] = true
// for i in 0..<A.count { 
    // checkArr[A[i]] == false {
        // checkArr[A[i]] = true
//    }
// }
// checkArr[i]가 false인 index 반환

public func solution(_ A : inout [Int]) -> Int {
    let size = A.count

    if size == 0 { return 1 }
    if size == 1 { return A[0] == 1 ? 2 : 1 }

    var checkArr = Array(repeating: false, count: size + 2)
    checkArr[0] = true // 1..<N+1의 범위이므로 0은 미리 true로 처리
    for i in 0..<A.count {
        if checkArr[A[i]] == false {
            checkArr[A[i]] = true
        }
    }

    if let idx = checkArr.firstIndex(where: { $0 == false }) {
        return idx
    } else {
        return 0
    }
}

더 나은 풀이

public func solution(_ A : inout [Int]) -> Int {
    var sum = 0
    
    let N = A.count
    let totalSum = (N + 1) * (N + 2) / 2  // N이 주어 졌을때 기대되는 전체 정수의 합을 구해줍니다. 보통 1~10까지의 합을 구하려면 (N+(N+1)) / 2로 계산할 수 있습니다.
    
    for element in A { // 현재 배열의 각 원소의 합을 구합니다.
        sum += element
    }
    
    return totalSum - sum  // 기대되는 원소의 합에서 실제 원소의 합을 빼면 비어있는 정수를 구할 수 있습니다.
}

// <https://jusung.github.io/Codility-Lesson3(Time-Complexity)-PermMissingElem/>