[Codility] OddOccurrencesInArray

안녕하세요:) 썸머입니다🏝

Codlity lesson2-2 문제를 풀어보았습니다.

 

문제

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

• the elements at indexes 0 and 2 have value 9,
• the elements at indexes 1 and 3 have value 3,
• the elements at indexes 4 and 6 have value 9,
• the element at index 5 has value 7 and is unpaired.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

• 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];
• all but one of the values in A occur an even number of times.

 

배열에서 짝을 이루지 못한 숫자가 무엇인지 구하는 문제입니다.

A의 범위가 10^9이기 때문에 O(N)~O(NlogN)의 시간복잡도로 문제를 해결해야합니다.

그래서 탐색하는 데에 O(N)인 배열 대신에 키값 탐색에 O(1)이 걸리는 딕셔너리를 사용해서 문제를 풀었습니다.

입력으로 받은 A = [9,3,9,3,9,7,9]의

원소 a가 딕셔너리 dict의 키값에 없다면 dict[a] = 1로 dict의 key에 추가하고

이미 키값에 존재한다면 딕셔너리에서 해당 원소의 키값을 삭제합니다.

dict[a] = nil 과 같이 딕셔너리의 (key, value)를 삭제하는 방법 외에도 dict.removeValue(forkey: a)라는 메소드도 있습니다.

 

문제의 조건에서 홀수개의 숫자는 딱 하나라고 명시했으니 반복문이 끝나고 나면

dict에는 하나의 키값만 남아있게 됩니다~!

func solution(_ A : inout [Int]) -> Int {
    let ret: Int
    var dict = [Int:Int]()
    A.forEach { a in
        if let _ = dict[a] {
            dict[a] = nil    // dict.removeValue(forKey: a)
        } else {
            dict[a] = 1
        }
    }

    ret = Array(dict.keys)[0]
    return ret
}

 

 

 

Summer풀이