コードテスト練習-フルコースを走っていない選手

プログラマーコードテスト練習:完全なコースを走っていない選手
参加者と完走者のリストがあります.一人を除いて、全部走ってしまった.完走していない参加者に戻る.

#エラーコード

初めて読み終わったら完走した人と参加者を比較して、完走した人を参加者リストから外して、残りの人をプリントアウトすればいいと思います.
結果は正しいが、効率は低い.
in listの結論は配列がすべて回転するのでfor文と同じであるためO(n^2)が必要である.

def solution(participant, completion):
    for i in completion:
        if i in participant:
            participant.remove(i)
            
    return participant[0]

#正解コード

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

2つのリストを並べ替えた後,順序に従ってマッチングを行い,マッチングしない参加者は完走者ではないと判断した.このコードは効率検査にも合格した.sort()演算には約O(NlogN)が必要であるため、O(NlogN)+O(NlogN)+O(N)=>O(NlogN)が必要となる.
このほかcollectionsとハッシュを用いてより効率的なコードを記述した人もいる.この場合、O(N)程度の時間が必要となるため、より効率的である.

*collections

import collections


def solution(participant, completion):
	# 완주자 명단에 없는 참가자만 반환
    answer = collections.Counter(participant) - collections.Counter(completion) 
    return list(answer.keys())[0]

*Hash

hashはdictionaryと同じ概念のようです.違いはhash概念自体に暗号化の側面があるため,hashを加えるとキー値が暗号化の任意の数字に変換される.

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer