[Codility Python] lesson 2 Arrays - OddOccurrencesInArray

문제링크

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

OddOccurrencesInArray coding task - Learn to Code - Codility

풀이

def solution(A):
    A.sort()
    l = len(A)
    for i in range(0, l, 2):
        # 인덱스의 끝이 답일 때 ex) 2 2 3 3 4
        if i == l-1:
            return A[i]
        if A[i] != A[i+1]:
            return A[i]

문제를 잘못 이해해서 시간을 많이 날렸다. array를 정렬하고 2스텝씩 진행했을때, 맞지 않으면 2스텝씩 묶은 첫번째 요소가 답이 된다. 하지만 만약 [2, 2, 3, 3, 4] 같은 경우는 마지막 요소를 짝을 묶을 수 없으므로 마지막 요소가 정답이 된다. 그래서 if i == l-1 조건문을 넣었다.

시간 복잡도는 O(N), O(N*log(N)) 이 나왔는데 더 줄이고 싶다...🙂 다른 사람의 풀이에서 xor 연산을 사용한 것을 봤는데 저런 두뇌회전.. 커비처럼 삼키고싶음.