티스토리 뷰

💻/CS

재밌는 ^ (xor) operator

사용자 eungding 2018. 11. 23. 11:07
728x90
반응형



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

}

728x90
반응형

'💻 > CS' 카테고리의 다른 글

codility 3-3. TapeEquilibrium 문제의 시간복잡도를 줄여보자  (0) 2018.11.26
재밌는 ^ (xor) operator  (0) 2018.11.23
댓글
댓글쓰기 폼