[Swift 알고리즘] FrogRiverOne - Codility

FrogRiverOne coding task - Learn to Code - Codility

---

요약

1. 문제를 꼼꼼히 읽자. 조건을 달성할 수 없는 경우 return -1 하라는 부분을 놓쳤다.
2. 예외 처리가 항상 아쉽다. 빈출 예외는 항상 고려하자 (0, 1, -1, 조건을 달성할 수 없는 경우, 극단값, …)

더 나은 풀이를 보고 …

1. Set을 활용하는 게 훨씬 간편하다.
2. 예외 처리를 할 때는 guard 문을 적극 활용하자.

접근

// 쉽게 느껴진다
// 배열을 탐색하며, 1...N에 해당하는 값이 최소 한 번씩 등장하는, 최소 시간을 구하는 것이다.
// 1. 무식하게 처음부터 탐색한다. O(N). 배열의 크기가 100,000 이하 이므로 가능하다.
    // cnt. checkArr 배열을 방문할 때마다 += 1
    // 1...N의 합을 구한다. totSum. 새로운 숫자를 탐색할 때마다 totSum에서 뺀다.
    // 1...N에 대응하는 checkArr를 생성한다. 방문할 때마다 totSum에서 제거하고, true로 바꾼다.
    // totSum == 0 && checkArr 배열이 모두 true인 경우 count를 return한다.

나의 풀이

import Foundation
import Glibc

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    let size = A.count
    if size < X { return -1 }
    var cnt = 0
    var totSum = X * (X + 1) / 2
    var checkArr = Array(repeating: false, count: X + 1)
    checkArr[0] = true // 1...size 범위만 사용하기 위함

    for i in 0..<size {
        cnt += 1
        
        if checkArr[A[i]] == false {
            checkArr[A[i]] = true
            totSum -= A[i]
        }

        if totSum == 0 && checkArr.filter({ $0 == false }).count == 0 {
            return cnt - 1
        }
    }

    return -1
}

더 나은 풀이

import Foundation

public func solution(_ X : Int, _ A : inout [Int]) -> Int {
    // write your code in Swift 4.2.1 (Linux)
    guard !A.isEmpty else { return -1 } //비어있는 배열은 존재할 수 없다.
    guard A.count >= X else { return -1 } //A의 개수가 X보다 작다면 절대 건너지 못한다.

    var leaves: Set = []
    var result = -1
    for (i, num) in A.enumerated() {
        leaves.insert(num)
        if leaves.count == X {
            result = i //index가 초임
            break
        }
    }

    return result
}

// <https://jeong9216.tistory.com/435#%EC%A0%84%EC%B2%B4-%EC%BD%94%EB%93%9C>