프로그래밍 면접 문제 18: Find Even Occurring Element
프로그래밍 면접 문제 18: Find Even Occurring Element
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 17: Search Unknown Length Array
나머지 모든 요소들은 홀수번 발생하고 하나의 요소만 짝수번 발생하는 정수 배열이 주어집니다. 이 배열에서 짝수번 발생하는 요소를 찾는 문제입니다.
횟수를 세는 것과 관련련된 문제를 해결할 때는 언제나 해시테이블을 사용할 수 있습니다. 배열을 확인하면서 각 요소가 발생한 횟수를 기록합니다. 그런 다음 해시테이블을 다시 확인해서 짝수번 발생한 요소를 반환합니다. 다음은 이에 대한 코드입니다.
def getEven1(arr):
counts=collections.defaultdict(int)
for num in arr:
counts[num]+=1
for num, count in counts.items():
if count%2==0:
return num
이 접근 방법의 시간 및 공간 복잡도는 O(N)이며, 최적화된 방법입니다. 이전 게시물인 Find Missing Element 에서 설명한 XOR 연산을 사용하면 효율은 동일하지만 좀 더 우아한 방법으로 문제를 해결할 수 있습니다. 먼저 set를 사용해서 배열 내 모든 고유한 숫자를 얻습니다. 그런 다음 원본 배열과 방금 얻은 고유 숫자를 모두 XOR 합니다. XOR의 결과는 짝수번 발생한 요소가 됩니다. 배열 내에서 홀수번 발생하는 요소들은 자기 자신과 홀수번 XOR 연산처리가 되어 결국 0이 되기 때문입니다. 또한 짝수번 발생한 유일한 숫자는 자기 자신과 XOR 연산이 짝수번 처리되기 때문에 그 숫자 자신이 됩니다. XOR 연산의 순서는 중요하지 않습니다. XOR 연산 횟수가 홀수이면 결과는 0이 되고, 짝수이면 해당 숫자가 그 결과가 됩니다. 그리고 여러 숫자가 있는 경우에도 XOR의 순서는 중요하지 않고, 단지 특정 숫자를 몇 번 XOR 연산 처리를 하는 지가 중요합니다.
예를 들어, [2, 1, 3, 1]의 숫자를 가진 배열이 있다고 가정해 보겠습니다. 먼저 고유한 요소인 [1, 2, 3]을 얻습니다. 그런 다음 원본 배열에 고유한 숫자를 추가해 다음과 같은 새로운 배열을 만듭니다 [2, 1, 3, 1, 1, 2, 3]. 이렇게 만든 새로운 배열 내 모든 수에 대해 XOR 연산을 합니다. 연산의 결과는 2^1^3^1^1^2^3 = 1 입니다. 숫자 2와 3은 새 배열에서 짝수번(2번) 발생하기 때문에 자기 자신과 홀수번(1번) XOR 되고, 연산의 결과는 0입니다. 숫자 1은 홀수번 (3번) 발생하기 때문에 자기 자신과 (2번) XOR 되고, 결과는 자기 자신인 1 입니다. 이는 원본 배열에서 홀수번 발생한 요소입니다. 이 접근 방법의 코드는 다음과 같습니다.
def getEven2(arr):
return reduce(lambda x, y: x^y, arr+list(set(arr)))
이 방법의 시간 및 공간 복잡도 역시 O(N)입니다. 참고로 해시테이블과 set에서 모두 삽입과 찾는데 걸리는 복잡도를 O(1)로 가정했으며, 이는 대부분의 경우에서 평균치 입니다. 하지만 사용하는 프로그래밍 언어와 구현 방법에 따라서 최악의 복잡도는 다를 수 있습니다. 이는 대수적이거나 선형 복잡도를 가질 수 있습니다. 하지만 면접 환경에서는 해시테이블과 set에서 모두 삽입과 검색을 하는데 일정한 시간이 걸린다고 가정해도 괜찮다고 생각합니다.
