[Codility] Lesson 2) OddOcurrencesInArray

코딜리티의 문제들은 무단 복제, 전재와 공개가 금지되어 있습니다. 때문에 문제의 개요와 제 코드만을 공개합니다.

풀이는 스위프트로 진행하였습니다.

---

문제의 개요

배열은 홀수로 구성되어 있고 각 요소는 자신과 같은 값을 가진 요소가 있습니다. 하나만 빼고요. 그 한 수를 리턴하면 됩니다. 이때, 자신과 같은 값을 가진 요소가 무조건 하나로 제한되는 건 아닙니다.

예를 들어 [1, 2, 3, 2, 1]이면 3이고 [1,1,1,1,2]면 2입니다. 

해답

1차 시도

public func solution(_ A : inout [Int]) -> Int {
    while true {
        if let pairIndex = A.lastIndex(of: A[0]) {
            A.remove(at: pairIndex)
            A.removeFirst()
        }
        if A.count == 1 {
            return A[0]
        }
    }
}

언뜻 보기에 매우 간단한 구조라 1분만에 후딱 짜봤습니다. 하지만 44점을 받았네요..

틀린 테스트 케이스는 extreme_single_item, small2, 큰 수로 가면 TIMEOUT ERROR가 발생했습니다.

타임아웃이 0.144인데 1.556초가 넘어가는 비효율적인 구조를 가지고 있기 때문에  사실 코드를 작성할 때부터 이런 식으로는 안 될거 같다는 생각을 했습니다. 거기에 답이 틀린건 왜 틀렸는지 고민해야 할듯합니다.

원인은 아마 remove와 removeFirst가 제일 커보입니다. inout으로 A가 주어졌기 때문에 해당 배열을 그대로 이용하고 싶었는데 이렇게 푸는게 아닌거 같네요. 

중복을 제거하는 방법이 생각났습니다.

 

 

2차 시도

public func solution(_ A : inout [Int]) -> Int {
    let SetA = Set(A)
    for num in SetA {
        let cnt = A.filter { ($0) == num }.count
        if cnt == 1 {
            return num
        }
    }
    return 0
}

Set과 filter를 이용하여 푼 코드입니다. Set으로 배열에서 중복된 값을 제외한 수를 추출하고 이를 이용하여 원래의 배열 A에서 중복되는 숫자를 세고 한개일 경우에만 해당 수를 리턴하면 됩니다.

근데 55% 짜리 코드였습니다. Correctness는 상승했지만 퍼포먼스도 그닥 올라가진 않았네요. 자동으로 감지된 복잡도는 O(N**2)이나 되서 다른 방법을 생각했습니다.

3차 시도

public func solution(_ A : inout [Int]) -> Int {
    var B = Set<Int>()
    for num in A {
        if B.contains(num) {
            B.remove(num)
        } else {
            B.insert(num)
        }
    }
    return B.first!
}

Set를 이용하는건 아무리 생각해도 맞는거 같지만 고차함수등을 사용하지 않고 문법적 요소로만 풀었습니다.

B는 Set이며 비어있습니다. 여기서 A를 순차적으로 가져와서 넣었다 뺐다 하면서 진행합니다. 원래는 배열로 풀어보려고 했지만 성능상 문제가 여전한거 같아 Set로 진행했습니다. 생각지도 못 한 부분이긴 했는데 Set 유용하네요.

복잡도도 O(N) or O(N * log(N))으로 만족스럽네요

 

글쓰는 시간까지 포함하면 30분 정도 걸린거 같습니다.