[Codility] OddOccurrencesInArray

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

주어진 리스트 A 중 짝이 없는 하나의 숫자를 리턴 문제
A의 원소의 개수가 최대 10억개이므로 O(n), O(logN) 혹은 O(NlogN)의 시간복잡도로 풀어야 할 것 같다.

나의 첫 번째 풀이(정답률 55%)

간단하게, A의 모든 원소를 확인하면서 list.count() 함수를 활용하여 count의 값이 1인 원소를 리턴하는 방법으로 풀어봤다.

def solution(A):
    # write your code in Python 3.6

    for i in A:
        if (A.count(i)) == 1:
            return i     

    pass

하지만 이는 O(n*n)의 시간복잡도를 가지는 풀이었다. n개의 원소를 가진 리스트에 count()가 n번씩 내부에서 loop를 도는 것 같았다

나의 두 번째 풀이(정답률 55%)

두 번째 풀이는 역시 리스트A의 전체를 돌면서 count()가 1이 아닐 시 filter()함수를 사용하여 해당 숫자를 제거한 리스트 A를 다시 생성하였다.

def solution(A):
    # write your code in Python 3.6
>
    for i in A:
        # print(A[i])
        if A.count(i) != 1:
            A = list(filter((i).__ne__, A)) # A리스트에서 i를 모두 제외한 리스트 생성
        else:
            return i
>
    pass

하지만 이 역시도 O(n*n)의 시간복잡도를 가졌다.

나의 세 번째 풀이(정답률 88%)

세 번째 풀이는 정렬을 활용하였다. 리스트 A를 정렬한 뒤 for문을 2step으로 돌면서 A[i]와 A[i+1]를 비교하였다. 하나의 숫자를 제외한 모든 숫자는 짝이 있으므로 짝수의 수를 가진다. 그러므로 2step으로 확인하다 보면 짝이 맞지 않은 숫자를 찾을 수 있다.

def solution(A):
    # write your code in Python 3.6

    A = sorted(A, reverse=True)
  
    for i in range(0, len(A), 2):
        if A[i] == A[i+1]:
            continue
        else:
            return A[i]

    pass

O(n*n)의 시간복잡도는 벗어났지만, 하나의 테스트케이스의 답을 맞추지 못했다.

나의 네 번째 풀이(정답률 100%)

A의 원소의 개수가 홀수개이고 하나의 원소만을 가진 값이 정렬된 리스트의 마지막에 놓였을 때, A[i] 와 A[i+]를 비교하게 되면 OutOfIndexError를 뱉게 된다. 그러므로, 이에 대한 처리가 필요하다.

def solution(A):
    # write your code in Python 3.6
    A = sorted(A, reverse=True) # 파이썬의 sorted()는 내부적으로 O(NlogN)의 시간복잡도를 가진다.

    for i in range(0, len(A), 2): # range(start, end, step)
        if i +1 == len(A): # 마지막 인덱스까지 갔을 때 해당 인덱스를 리턴
            return A[i]

        if A[i] == A[i+1]:
            continue
        else:
            return A[i]

    pass