Lesson 2 : Arrays - OddOccurrencesInArray

문제 링크 : https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

Non-empty 배열 A가 주어지고, A는 홀수 개의 원소를 가집니다. 모든 원소들은 단 하나를 제외하고 모두 쌍을 이룹니다. 예를 들어, A = [1, 3, 2, 4, 1, 3, 2]라고 하면 1, 2, 3은 배열 내 원소가 짝수 개여서 pair를 이루지만 4의 경우에는 pair를 만들 수 없습니다. 이 때 해당 value인 4를 return하면 됩니다.

def solution(A):
    unique = set(A)
    for i in unique:
        if A.count(i) % 2 == 1:
            return i

처음에는 아무 생각 없이 list.count를 사용했는데 이 때의 detected time complexity가 O(N^2)가 나와 performance 점수를 25점밖에 받지 못했습니다. 모든 원소에 대해 배열을 한 번씩 훑어야 개수를 셀 수 있으니 저런 time complexity가 나오는게 맞습니다.

 

def solution(A):
    sort = sorted(A)
    
    num_check = 1
    for i in range(len(sort)-1):
        if sort[i] == sort[i+1]:
            num_check += 1
        else:
            if num_check % 2 == 1:
                return sort[i]
            else:
                num_check = 1
                
    if num_check % 2 == 1:
        return sort[i]

방법을 바꿔서, 우선 주어진 list를 정렬시키고, 처음부터 훑으면서 원소의 개수가 짝수가 아닌 경우에 바로 해당 value를 return하도록 해서 통과했습니다. 이 경우 detected time complexity는 O(N) or O(N*log(N))이 나옵니다. 사실상 원소를 훑는 것보다 정렬하는데 시간이 더 오래 걸릴 수 있겠죠.