[Algorithm] FrogRiverOne

[hwangJi-dev]

💬 문제

https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

💬 Idea

1. 처음에는 X 크기를 가진 배열을 false로 모두 초기화하여 생성한 뒤, 반복문을 돌며 해당 인덱스의 값을 true로 바꾼 후 조건문을 통해 해당 배열이 모두 true인지 검사해주는 작업을 거쳤었다. 그러나 이렇게 하니 반복문 안에 O(N)의 시간복잡도를 가지는 작업이 들어있어 시간 초과가 발생했다.
2. 따라서 풀이 접근법을 조금 변경하여 Set 자료구조를 사용했다. 문제의 조건에서 배열의 원소의 값은 무조건 X + 1 이내의 수라 했으므로 Set에 차례로 원소를 집어넣은 후 해당 배열의 count가 X와 동일해질 때를 검사하여 해당 시간을 리턴해주었다.
   1. count 비교는 O(1)의 시간복잡도를 가지므로 훨씬 효율적이다.

💬 풀이

public func solution(X : Int, A : inout [Int]) -> Int {
    var leafArr: Set<Int> = []
    
    for (idx, i) in A.enumerated() {
        leafArr.insert(i)
        if leafArr.count == X { return idx }
    }
    
    return -1
}

소요시간 : 15분

시간 복잡도 : O(N)

평가표 : https://app.codility.com/demo/results/trainingXMSU6T-TQB/