[코딜리티] 레슨 2 - Odd Occurrences In Array (Swift)

직접 풀었을 때 사용한 해시맵을 이용한 풀이:

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

    for num in A {
        if let value = frequencyMap[num] {
            frequencyMap[num] = nil
        } else {
            frequencyMap[num] = true
        }
    }

    for (key, value) in frequencyMap {
        if value == true {
            return key
        }
    }

    return -1
}

위 풀이에서는 주어지는 Array를 1번 순회하고 다시 한번 frequencyMap을 순회하는 과정에서 O(2N) 의 시간복잡도가 생긴다.

통과는 했지만 한번만 순회해서 O(N)의 시간복잡도를 가지는 좀 더 효율적인 풀이는 없을까 고민해봤다.

잠깐 고민해보니 이런 방법이 떠올랐다:

만약 한번 순회하는 동안 같은 숫자가 나타나면 빼고, 없는 숫자가 나타나면 더할 수만 있다면 결국엔 짝이 없는 홀수만 남을 것이다.

그렇지만 더할지 뺄지 알려면 이미 나타난 적이 있는지 아닌지 여부를 알아야하고, 이를 알려면 frequencyMap을 사용한 것과 같이 별도로 변수를 만들어 기록이 필요할 것이라 생각했다.

약간의 검색을 통해 별도의 변수를 쓰지 않고 위와 같은 방법으로 1회 순회해서 풀이하는 방법을 찾을 수 있었다.

바로 Bitwise XOR (exclusive OR) Operator를 쓰는 방식이었다.

public func solution(_ A : inout [Int]) -> Int {
    var result = 0
    
    for number in A {
    	result ^= number
    }
    
    return result
}

어떤가? 매우 간단해지지 않았나?

Bitwise XOR Operator는 간단히 얘기하면 이미 있는 값은 상쇄해서 0으로 만들어주고 없는 값은 추가해준다.

Bitwise XOR Operator는 스위프트 공식문서에 자세하게 설명되어있다.

https://docs.swift.org/swift-book/documentation/the-swift-programming-language/advancedoperators/#Bitwise-XOR-Operator

Bitwise 연산에 대해 거리감이 좀 있었는데, 이번 경험을 통해 조금 더 가까워진 느낌이다.

추후에 다른 Bitwise 연산 문제들을 접하면 이전보다 적극적으로 다가갈 수 있을 것 같다.