Codility - Odd Occurrences In Array

A는 N개의 정수로 이루어진 비어있지 않은 배열입니다. 배열의 요소들의 개수는 홀수개입니다. 한 개의 요소를 제외하고는 모두 짝을 이룰 수 있습니다.

예를 들어 다음과 같은 배열 A가 있습니다.

  A[0] = 9  A[1] = 3  A[2] = 9
  A[3] = 3  A[4] = 9  A[5] = 7
  A[6] = 9

• 0과 2의 위치의 요소는 9
• 1과 3의 위치의 요소는 3
• 4와 6의 위치의 요소는 9
• 5번째 위치의 요소는 7이고 짝을 이루지 않습니다.

이런 경우 함수는 7을 리턴하면 됩니다.

다음 가정에서 효과적인 알고리즘을 작성하세요.

• N은 홀수개이고 1~100만 안에 있는 숫자입니다.
• A의 각 요소는 정수이고 1~1,000,000,000의 범위를 가집니다.
• A의 값 중 하나를 제외하고 모두 짝수개입니다.

 

풀이

def solution(A):
    count = {}
    for a in A:
        if a in count:
            count[a] += 1
        else:
            count[a] = 1

    for (k, v) in count.items():
        if v % 2 == 1:
            return k

각 요소의 개수를 세고 홀수개인 요소를 찾으면 됩니다. 반복문이 중첩되지 않기 때문에 효율성은 O(N)입니다.

 

각 요소의 개수를 세는 쉬운 방법은 collections 모듈에 있는 Counter 클래스를 사용하는 방법입니다.

from collections import Counter

def solution(A):
    count = Counter(A)

    for (k, v) in count.items():
        if v % 2 == 1:
            return k