프로그래밍 면접 문제 22: Find Odd Occurring Element
프로그래밍 면접 문제 22: Find Odd Occurring Element
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 21: Tree Reverse Level Order Print
정수 배열이 주어지면, 나머지 요소들은 모두 짝수번 존재하는데 하나의 요소만 홀수번 존재합니다. 여기에서 홀수번 존재하는 요소를 찾습니다.
이 문제는 전에 포스팅 했던 find even occurring element 문제와 매우 유사합니다. 그리고 같은 해결 방법을 사용할 수 있습니다. 한 가지 접근 방법은 요소들이 배열에 발생한 횟수를 기록하는 해시테이블을 생성한 다음 홀수번 발생한 요소를 반환하는 것입니다. 이 방법의 시간 및 공간 복잡도는 모두 O(N)입니다.
하지만 이전 포스트에서 설명했던 XOR 기법을 사용해서 더 좋은 방법으로 문제를 해결 할 수 있습니다. 원리는 다음과 같습니다: 특정 숫자가 자기 자신과 XOR 연산이 홀수번 처리되면 그 결과는 0이고, XOR 연산이 짝수번 처리되면 그 숫자를 결과로 얻습니다. 따라서, 배열 내 모든 요소에 대해서 XOR 연산을 하면 결과는 홀수번 존재하는 요소를 결과로 얻을 수 있습니다. 그 이유는 짝수번 존재하는 요소들은 자기 자신과 홀수번 XOR 처리되어 0을 생산하기 때문입니다. 홀수번 존재하는 요소는 자기 자신과 짝수번 XOR 처리되어 해당 숫자가 결과로 생성됩니다.
[1, 2, 3, 1, 2, 3, 1] 배열이 주어졌다고 가정해 보겠습니다. 배열 내 모든 요소들에 대해 XOR 연산 처리하면 결과는 1^2^3^1^2^3^1 = 1 입니다. 2와 3은 자기 자신과 1번 XOR 처리되기 때문에 0이 됩니다. 그리고 1은 자기 자신과 2번 XOR 처리되기 때문에 연산의 결과로 자기 자신인 1이 됩니다. 따라서, 전체 XOR 연산의 결과는 배열 내에서 홀수번 존재하는 요소인 숫자 1이 됩니다. 코드는 다음과 같습니다:
def getOdd(arr):
return reduce(lambda x, y: x^y, arr)
너무나 간단합니다. 이 해결 방법의 시간 복잡도는 여전히 O(N)이지만, 공간 복잡도는 일정하게 O(1)입니다. 일정한 여분의 메모리를 사용하고 입력된 배열의 크기에 비례하는 크기를 사용하지 않기 때문입니다. 이 해결 방법은 모든 요소에 한번씩만 접근하고 일정한 크기의 공간만 사용하기 때문에, 가장 최적화된 솔루션입니다.
이 문제는 비트 연산의 강력함과 효과를 보여주는 문제이기 때문에 훌륭한 문제입니다.
