[Codility] 2. OddOccurrencesInArray

문제 링크
OddOccurrencesInArray

문제 요약
N is an odd integer within the range [1..1,000,000]
each element of array A is an integer within the range [1..1,000,000,000]
위와 같이 Array 및 범위가 주어진다
같은 값으로 한 쌍 혹은 그 이상씩 존재하지만 단 하나의 수는 짝을 이루지 않고있다
그 때 짝을 이루지 못한 수를 구하자

요구사항
이중 for문을 사용했더니 시간초과가 발생
(Array의 Element 수가 Max 100만 -> N^2의 경우 시간초과)
순서가 없고 중복을 허용하지 않는 Set을 이용하거나 Dictionary key, value 이용

코드

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var unPairedNum = Int()
    var pairChecked = [Int:Int]()

    for i in 0..<A.count {
        pairChecked[A[i], default: 0] += 1
    }

    for (key, pairedCnt) in pairChecked {
        if( pairedCnt % 2 == 1 ) {
            unPairedNum = key
        }
    }

    return unPairedNum
}

시간복잡도
앞서 A.count만큼 전체 데이터를 순회하므로 O(N)
각 순회당 key의 존재여부를 탐색하는데 O(logN)
결과적으로 O(NlogN)