OddOccurrencesInArray - Easy(배열, Codility)

def solution(A):
    if len(A) == 1:
        return A[-1]
    stack = []
    A.sort()
    for i in A:
        if len(stack) == 0:
            stack.append(i)
        elif i == stack[-1]:
            stack.pop()
        else:
            stack.append(i)
    return stack[-1]

 

처음에는 그냥 count를 써서 2의 나머지가 1인 값을 구하게했으나 효율성에서 계속 떨어졌다.

 

이유를 찾아보니 count() 함수는 O(n)의 시간복잡도를 가지는데 이를 각 배열의 인자마다 사용하니 시간복잡도가 n의 제곱만큼 들었다.

 

결국 sort로 연속되는 값이 나오게 세팅하고 stack으로 각 값이 같은 경우만 pop()해주는 방식으로 최악의 경우 O(n) 최선의 경우 O(n log n)의 시간복잡도를 가지게 되었다.

 

앞으로 간단한 문제는 스택으로 잘 해결하자.