리스트 내 쌍을 이루지 않은 정수값 찾기 소스

findunpairedvlue.py

def findUnpairedValue(list) : #리스트 내 쌍을 이루지 않은 정수값
    list.sort() #리스트 값을 정렬한다.
    #리스트 범위 내에 2개의 값씩 서로 같은지 비교한다.
    #이미 정렬을 했기 때문에 쌍을 이루는 값일 경우 해당 순서값과 다음값이 서로 같아야 한다.
    #다들 경우 해당 값은 쌍을 이루지 않고 있으므로, 해당 값을 바로 리턴.
    #시간복잡도 O(N) or O(N*log(N))
    cnt = len(list)
    i = 0
    while i < cnt :
        if (i+1) >= cnt or list[i] != list[i+1]:
            return list[i]
        i += 2
    return 0

listArr = [3,3,4,4,5]
print(findUnpairedValue(listArr))


###아래 소스도 동일한 기능을 한다.
###단, 아래 소스는 리스트를 정렬을 하지 않고, 리스트 값 별로 루프를 돌면서,
###해당 값이 루프 내 몇개가 있는지를 체크한 후 홀수개인 수를 리턴.
###루프 내 COUNT 역시 다시금 배열을 체크하는 함수이므로 결국 이중 루프의 효과.
###이로 인해 O(N**2) 의 시간복잡도가 되어 리스트가 커지면 시간이 무한히 커진다.
###그러므로 위의 1차 정렬 후 비교 하는 소스를 활용
#def findUnpairedValue(list):
#    for val in A :
#        if A.count(val)%2!=0 :
#            return val
#    return 0;