Codility - Lesson 2 OddOccurrencesInArray

Codility 2번째 Lesson에 OddOccurrencesInArray 입니다.

이 문제는 N개의 데이터를 가지는 Intarray에 동일한 값을 갖지 않는 값을 반환하는 문제 입니다. 문제의 자세한 내용은 여기서 확인하시면 됩니다.

 

그럼 해결 방법을 보겠습니다.

fun solution(A: IntArray): Int {
    // write your code in Kotlin
    var count = 0
    var ans = 0;
    for( i  in 0 .. (A.size-1)){
        var isPair = false
        for( j in 0 .. (A.size-1)){
            if(i != j){
                if(A[i] ==A[j]){
                    isPair = true
                    break;
                }
            }
        }
        if(!isPair){
            ans = A[i]
            break;
        }
    }
    return ans
}

간단하게 반복체크를 하여 동일한 값이 나오면 그만 두고 안나오면 그 결과 값을 ans대입하여 반환하였습니다. 하지만 이 경우에는 A의 size가 엄청 클경우 문제가 되어 결과가 해결 결과가 55%밖에 되지 않았습니다. 그래서 다시 해결해보았습니다.(아마 이중 for문을  쓸 경우 빅O복잡도에 의해 만약 A의 size 가 1,000,000,000일 경우에 1,000,000,000^2 번 동작하기 때문에 그런것 같습니다.)

그래서 다양한 방법으로 도전 했는데 도통 100%가 나오지 않아 구글의 힘을 빌렸더니 XOR 연산으로 해결들을 하였습니다.

fun solution(A: IntArray): Int {
    // write your code in Kotlin
    
    var result = 0;
    for(i  in A.indices){
        result = result xor  A[i]
    }
    return result
}

 

XOR의 개념은 

비트연산을 할 때 1이 홀수개이면 1 짝수 개이면 0이 나옵니다.

그래서 1010^1010 =0000 1010^1010^1010 = 1010

그래서 자기자신과 짝수번 연산하면 0이 되고 홀수번 연산하면 자기자신이 됩니다. 이 문제에서 XOR을 쓸 수 있었던 이유는 반복되지 않는 수를 뽑을 수 있기 때문입니다.

 

이번 기회로 비트연산자를 다시한번 공부하고, 왠만하면 2중 for문을 쓰지 않는 것이 성을에 좋다는 것을 다시한번 느꼈습니다.