アルゴリズム問題の解-ハッシュ

プログラマ

完走していない選手

def solution1(participant, completion):
    participant.sort()
    completion.sort()

    answer = ''
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            answer = participant[i]
            break;

    else:
        answer = participant[len(participant) - 1]

    # print(answer)

    return answer

def solution2(participant, completion):
    answer = ''
    data = dict()
    for i in participant:
        if i in data.keys():
            v = data[i]
            data[i] = v + 1

        else:
            data[i] = 1

    for i in completion:
        v = data[i]
        data[i] = v - 1

    for k, v in data.items():
        if v != 0:
            answer = k

    return answer

電話番号リスト

Sort後のダブルfor文による全面比較->時間複雑度エラー(解決方法X)

文字列にソートされているため、起動後すぐに前に比較するだけです.前に比較するだけです.

def solution(phone_book):
    answer = True


    # 방법 1 (시간 초과)
    # phone_book.sort()
    # for i in range(len(phone_book)):
    #     for j in range( i +1 ,len(phone_book)):
    #         if phone_book[j].startswith(phone_book[i]):
    #             return False

    # 방법 2 (sort를 이용하여 바로 앞만 확인)
    # phone_book.sort()
    # for i in range(len(phone_book)-1):
    #     if phone_book[i+1].startswith(phone_book[i]):
    #         answer=False

    # 방법 3. (해시를 이용)
    data = dict()
    for i in phone_book:
        data[i] = 1

    for num in phone_book:
        temp = ""
        for j in num:
            temp += j 
            if temp in phone_book and temp != num: 
                answer = False



    return answer