Codility - odd_occurrences_in_array[Python]

😅 문제 

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

🤔 문제 상황 

- 홀수들을 요소로 가진 배열이 있는데 한 개를 제외한 모든 요소는 짝수개의 짝을 이룬다.

- codility는 속도 이슈에 민감해 문제가 있었다.

  

 

🧐 해결 전략 

- 처음 생각한 전략은 단순히 배열을 스캔하면서 새로운 것이 나오면 check 리스트에 넣고, 이미 check 리스트에 있는 값이 나오면 그 값을 제거하는 식으로 했다. 하지만 문제는 제거하는 과정 자체에 O(N)의 스캔이 필요하므로 N*2 의 소요시간이 발생해 시간 초과가 났다. 즉, N의 길이를 가진 for문 안에서 remove를 사용하면 N*2 의 시간초과가 발생할 수밖에 없다.

- 두번째로 생각한 전략은 아예 check list를 0으로 초기화해서 새로운 수가 나오면 1로 버튼을 켜고, 두번째 나오면 다시 끄는 전략이었다. 하지만 수의 범위가 1000,000,000 으로 이를 초기화 하니 메모리 에러가 발생했다. 배열을 만들기에 너무 큰 숫자였다.

- 그래서 세번째로 생각한 것이 dictionary 구조를 이용한 것이었다. dictionary에 값을 업데이트하거나 추가하는 것은 시간 소요가 많지 않으므로 해당 방법을 사용하였다. 

- 또 발생한 문제는 코드 자체를 짤 때, 4번 나오는 요소나 3번 나오는 요소처럼 이미 꺼진 것에 다시 켜지는 업데이트를 생각하지 않아서 발생했다.

🎰 코드 

def solution(A):
    ck = {}
    for i in range(len(A)):
        if A[i] not in ck :
            ck[A[i]] = 1
        elif ck[A[i]] :
            ck[A[i]] = 0
        elif not ck[A[i]] :
            ck[A[i]] = 1
    cklist = sorted(list(ck.items()), key = lambda x : -x[1])
    return cklist[0][0]

 

🧙‍♂️ 해설

- 리스트 A를 스캔하며 ck 딕셔너리에 값이 없으면 1로 생성, 있는데 값이 1이면 0으로 업데이트, 있는데 값이 0이면 1로 업데이트 한 후 최종적으로 dictionary의 value 값을 내림차순으로 정렬해주면 1인 값이 하나 뿐이므로 첫번째 값의 key가 답이 된다.

📈 새로 학습한 것 & 실수 

- if 구문에서 if True 의 반대를 만들고 싶으면 if not True 해야한다. !로 하는 것이 아니다.(자바랑 헷갈림)