[Swift 알고리즘] OddOccurrencesInArray - Codility

https://app.codility.com/programmers/lessons/2-arrays/

2. Arrays lesson - Learn to Code - Codility

---

요약

간단한 문제임에도 문제 접근에 시간이 꽤 걸렸다. (15분)

unpaired value는 1개만 나온다고 착각했지만, 홀수개였다. 문제를 잘 읽자.

XOR에 대하여

더 나은 풀이에 대한 내용이다.

XOR 연산자는 다음과 같은 특성이 있다.

같은 수를 XOR 연산하면 없어진다. 순서는 상관 없다.

3 == 0011

5 == 0101

1 == 0001

• 3^5^5 == 0011 (3)
• 3^5^5^3 == 0000
• 3^3 == 0000
• 3^3^5 == 0101 (5)
• 3^1^3^1^3^1^3^1^5 == 0101 (5)

검색한 것

• dictionary 내에 key 여부를 파악하는 법
  • Swift의 기본 기능으로 없으면 nil을 반환한다
• dictionary의 첫 번째 원소의 key를 반환하는 법
  • .first! / .last! (딕셔너리는 기본적으로 옵셔널을 반환하므로, forced-unwrapping)
  • .key / .value

나의 풀이

// A 배열의 길이는 1 ~ 1,000,000 이하 
    // -> Empty 배열에 대한 처리는 따로 하지 않아도 좋다
    // NlogN까지만 괜찮다
// 원소는 1 ~ 1,000,000,000

// 한 번만 나오는 원소를 출력하면 되지 않는가?
// 배열을 전부 탐색하면서 원소를 cnt 한다.
    // 딕셔너리에 해당 키가 없으면, 키를 생성하고 cnt = 1
    // 키가 있으면, cnt += 1
// 탐색을 종료하면, 딕셔너리를 값을 기준으로 정렬하여, 최소 값의 키를 반환한다.

import Foundation
import Glibc

public func solution(_ A : inout [Int]) -> Int {
    var countDict: [Int: Int] = [:]
    A.forEach {
        if countDict[$0] != nil {
            countDict[$0]! += 1
        } else {
            countDict[$0] = 1
        }
    }

    let sortedCountDict = countDict.filter { $0.1 % 2 != 0 }
    
    return sortedCountDict.first!.key
}

더 나은 풀이

public func solution(_ A : inout [Int]) -> Int {
    return A.reduce(0){ $0^$1 }
}

// 어이 없는 풀이 ㅋㅋ