재밌는 ^ (xor) operator

 

 

XOR ( ^ ) 은  두 값을 이진수로 바꾼 후, 두 값의 각 자리수를 비교해서 같으면 0, 다르면 1 을 계산하는 비트 연산자이다 : ) 

 

 

ex) 

 

3 = 0011

5 = 0101 

1 = 0001 

 

3^5 = 0110

 

 

 

 

 ^ 연산자에는 재밌는 속성이 있다 

 

3^5^5 = 0011 (십진수:3)

3^5^5^3 = 0000 

 

3^3 = 0000

3^3^5 = 0101 (십진수: 5)

3^5^3 = 0101 (십진수: 5)

 

3^3^5^1 = 0100

3^3^5^1^1 = 0101 (십진수:5) 

 

 

 

✅ 같은 수를 두번 xor연산하면 없어진다 

✅ 근데 같은 수 두번의 위치는 상관없다 ( 두 값이 서로 붙어있든, 떨어져있든 ) => 나눗셈과 비슷하다 

 

 

 

이런 xor연산자의 속성을 활용하면 

 

codility - OddOccurrencesInArray 

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

 

이 문제를 시간복잡도 O(N)으로 풀수 있다!!! 

 

이렇게 한 줄이면 끝난다 >___< 

 

 

public func solution(_ A : inout [Int]) -> Int {

    return A.reduce(0){$0^$1}

 

}

 

 

 

 

이 연산자가 없이 다른 방법으로 코드를 짜면  O(N**2) 의 시간복잡도가 나오는데ㅠㅠㅠ xor 짱짱 

 

public func solution(_ A : inout [Int]) -> Int {

    // write your code in Swift 3.0 (Linux)

    

    var A = A

    let candidates = Array(Set(A))

    

    for item in candidates{

        

        let subArray = A.filter{$0 == item}

        if subArray.count % 2 == 1{

            return item

        }

        

        // item에 대해 작업을 다해주고 배열에서 싹 다 제거

        A = A.filter{$0 != item}

    }

    

    return 0

 

}

 

 

public func solution(_ A : inout [Int]) -> Int {

    // write your code in Swift 3.0 (Linux)

    if A.count == 1 {return A[0]}

    

    let A = A.sorted(by: <)

    

    let indexArray = Array(0...A.count-1).filter{$0 % 2 == 0}

    

    for i in indexArray{

        

        if i == A.count - 1 {return A[i]}

        

        if A[i] != A[i+1]{

            return A[i]

        }

    }

    

    return 0

 

}