[알고리즘][Codility] OddOccurrencesInArray

문제는 아래 링크에서 확인 가능합니다.

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

문제를 간단히 요약하면 N개(홀수 개)의 배열에 Int 정수들이 있는데, 각각이 쌍이 있습니다. 그런데 그 중 하나의 숫자가 홀로 들어 있는 것이 있는데 그 숫자를 찾아내라는 것이 문제입니다.

예를 들어 배열에 [9, 3, 9, 3, 9, 7, 9] 와 같이 있으면, 7만 유일하게 쌍이 없이 홀로 있습니다. 따라서 7을 return 해주면 됩니다.

제가 최초 작성한 코드는 다음과 같습니다.
(참고로 코드는 Kotlin으로 풀었습니다. Codility에서는 최근 Kotlin도 지원합니다!)

fun solution(arr: IntArray): Int {
    arr.sort()
    val set = arr.toSet()
    set.forEach { v ->
        if (arr.filter { it == v }.size % 2 == 1) {
            return v
        }
    }

    return 0
}

제출했더니… 66%로 나옵니다.
N이 100,003인 경우 timeout이 발생하였습니다.
시간 복잡도는 O(N ^ 2) 으로 나오고요.

제 머리로는 사실상 포기입니다.
timeout이 0.3초인데, 제 결과는 Local 환경에서 6초대에 머물렀습니다.
도무지 0.3초대로 줄일 수 있는 방법이 떠오르지 않습니다.

이 정도의 성능 차이는 애초에 접근법이 다르다는 건데요. 포기하고 솔루션을 찾아봤습니다. 결과적으로 전혀 생각지 못했던 방법입니다.

우선 솔루션 코드부터 보시면 다음과 같습니다.

fun solution(arr: IntArray) = arr.reduce { num1, num2 -> num1 xor num2 }

???

코드를 쓰다 말았냐고요?
아닙니다.
단 한줄로 100% 패스하였습니다.
6초가 걸리던 작업이 불과 23ms에 완료되었습니다.

O(N ^ 2)으로 나오던 시간 복잡도는 O(N) or O(N*log(N))으로 개선되었습니다.

핵심은 xor 연산에 있었습니다.
xor 연산이 무엇인가요?

A	B	XOR
0	0	0
1	0	1
0	1	1
1	1	0

2 숫자가 서로 다를 때에만 1이고 같을 경우는 0입니다.
문제 자체가 배열 속에 서로 쌍이 되는 숫자들이 있고, 이 중 홀로 존재하는 숫자를 찾아내는 것이기 때문에 XOR연산을 거치다 보면 쌍이 되는 숫자는 XOR 연산을 통해 0이 되고 결국 홀로 존재하는 숫자만 남게 됩니다.

그렇기 때문에 O(N) or O(N*log(N)) 이라는 경이로운 시간 복잡도를 달성할 수 있게 됩니다.

개인적으로 이런 비트 연산자를 다룰 일이 없다보니 등한시했는데, 이번 기회를 통해 그 중요성을 다시 돌아보게 되었습니다.