codibility - OddOccurencesInArray

문제

• Array에서 element 값이 pair가 되지 않는 경우의 value 반환

내 코드

from collections import Counter

def solution(A):
    cnt_A = Counter(A)
    for key, value in cnt_A.items():
        if value % 2 == 1:
            return key

• 이럴 때 유용한 게 Counter
• 하지만 이 경우 공간 복잡도가 O(N)
  • 시간 복잡도는 전체를 한 번만 보면 되니까 O(N)

지피티 코드

def solution(A):
    result = 0
    for number in A:
        result ^= number
    return result

• XOR 계산으로 한 번에 해결
  • 같은 수끼리 XOR: 0
  • 0과 XOR: 자기 자신
• 천재적인 생각 ... 난 절대 생각 못할 것 같음 ㅎ