[Swift] FrogRiverOne 문제 풀이 [Codility - Lesson4. Counting Elements]

💬 문제

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

FrogRiverOne coding task - Learn to Code - Codility

 

---

💬 Idea

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

 

시간 복잡도 : O(N)

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

Test results - Codility

 

 

 

https://github.com/hwangJi-dev/swiftAlgorithm/blob/main/Programmers/Codility/Counting%20Elements/FrogRiverOne.swift

GitHub - hwangJi-dev/swiftAlgorithm: Algorithm Practice with Swift