フルコースを走っていない選手[第1級]Python(データ構造解析を用いる)

1819 ワード
programmers Level 1 python 亥時 テキストリンク

問題の説明


多くのマラソン選手がマラソンに参加した.1人の選手を除いて、すべての選手がマラソンを完走した.
マラソンに出場する選手の名前と完走した選手の名前の並びが完成したら、完走していない選手の名前を返す解決関数を書いてください.

せいげんじょうけん

  • マラソンに出場する選手は1人以上10万人以下.
  • 完了長さは参加者長1より小さい.
  • 参加者の名前は20文字を超えない.
  • の参加者には同名の人がいる可能性があります.

    • I/O例



    I/O例説明


    例1
    「leo」は参加者名簿に載っているが、フルコースを走る者名簿には載っていないため、フルコースを完走できなかった.
    例2
    「vinko」は参加者名簿に載っていたが、完走者名簿に載っていなかったため完走できなかった.
    例#3
    「誤導」は参加者リストに2人いたが、完走者リストには1人しかいなかったため、1人は完走しなかった.

    ハッシュとは?(データ構造)


    ハッシュはデータを処理する技術で、検索と記憶速度が非常に速い!迅速に行えるのは,データの検索に用いられるキーと実際のデータの値がペアであり,キー値が配列のインデックスであるため,検索と格納の平均時間複雑度はO(1)に収束する.

    私が書いたコード

    def solution(participant, completion): 
    # 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주
    # 참가자 중에는 동명이인이 있을 수 있습니다. 
    # 효율성 테스트 성공
    answer = ''
    participant, completion = sorted(participant), sorted(completion)
    #print(participant, completion)
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
        
    return participant[-1]

    詩を解く

    import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion) # Collections 차집합
    return list(answer.keys())[0]
    私が解詩で書いた解(効率淘汰)
        answer = ''
    _answer = list(set(participant) - set(completion))
    if len(_answer) != 0: answer = _answer[0]
    
    for name in completion: O(n)
        if participant.count(name) >= 2: #.count() -> O(n) ==> O(n^2)
            answer = name
                
    return answer
    Java実装Stack,Queue,BinaryTree
    LeetCode String to Integer (atoi)