(코딜리티) Lesson 2 : OddOccurrencesInArray - Python

이 문제는 효율성에서 100%가 안나와서 고민하다가, 어찌어찌 해결하긴 했습니다만..

혹시나 다른 사람들의 코드를 보고 싶어서 보는 산업공학도로서는 순간 경악을 금치못했네요...

 

세상엔 진짜 똑똑한 사람이 너무 많은 것같습니다.. 

 

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

OddOccurrencesInArray coding task - Learn to Code - Codility

문제설명

N개의 배열 A를 주어질 때, 그 배열의 갯수는 홀수입니다. 각 요소들은 하나의 쌍으로 이루어져 있지만, 하나는 쌍을 이루어지지 않습니다. 그 하나의 값을 return하시오.

 

예를 들어 [9, 3, 9, 3, 9, 7, 9] 일때, 7을 제외한 나머지 값은 쌍을 이루므로 7을 return합니다.

제한 사항

N은 1~1,000,000 사이의 홀수 값

A의 각요소는 1~1,000,000,000사이의 값

A에서 단 하나의 값을 빼고는 모두 짝수 번 발생합니다.

코드 

def solution(A):
    
    A = sorted(A)

    while A:
        try : 
            a = A.pop()
            b = A.pop()
        except : 
            break

        if not a == b:
            break
            
    return a 

위코드는 통과한 코드지만, 제일 처음 통과하지 못했던 코드는 아래에 있습니다.

def solution(A):
 
    while A:
        a = A.pop()
        if a in A:
            A.remove(a)
        else :
            break

    return a

O(N**2)의 시간복잡도로, 효율성 통과를 못했습니다.

아마 if문에서 N시간, A.remove에서 N시간으로 통과하지 못한 것 같습니다.

그래서, 생각한 것이 처음에 정렬하고 첫번째 두번째 비교하고 2개는 버리는 식으로 쌍을 이루어 비교하다보면, 값이 다른 두개의 값에 처음이 쌍을 이루지 못한 값이라고 생각했습니다.

 

try부분은 마지막 까지 확인하고 1개남았을 때 에러발생때문에 try문을 사용했습니다.

 

if문은 중간에 하나만 남아있는 값이 있을 때 바로 끝내기 위해 사용했습니다.

 

그렇게 전자의 코드로 통과하였습니다.

 

보고 놀란 다른사람의 코드

from functools import reduce

def solution(A):
    return reduce(lambda x,y: x^y, A)

python3 부터는 reduce를 import해야한다고 합니다.

어떻게 이진수로 XOR을 하다보면 결국 마지막에 남는 값은 쌍이 되지 못한 값이 나온다는 것을 어떻게 생각할수가 있을까요..

도대체 위와 같은 생각을 하기위해서는 어떤근본을 알고 있어야 저런 생각이 가능한지...

진짜 전 위 코드를 보고 경악을 금치못했습니다...

어떻게 사람머리에서 저게 가능할까.. 어느 부분에 원리를 알면 생각을 할 수 있을까...