✔アルゴリズム/プログラマー/ハッシュレベル2/電話番号リスト(Python使用)

9541 ワード
アルゴリズム問題 programmers 亥時 テキストリンク

📖 質問する



📝 解法

  • リストphone bookをソートします.
    前の字は同じでなければなりませんが、接頭辞である可能性が高いので、ソート後だけ前の字が似ています.
  • は、新しいディックシャーナの価格を設定します.
    keyは電話番号の最初の数字を含み、valueはkeyを最初の数字の電話番号リストとして含む.
  • ディック郡の例)
  • データのキーを押して値をループします.
    巡るときは、前の数が後の数の接頭辞として使えるかどうかを確認します.
    ->これは、リストphone bookが整列しているため、ディクソンデータ値に入る値も整列していることを保証します.
    • コードが少し乱れていますが...答えはfalseですが、残りのfor文がすべて返されないように
    if answer == False :
    break
    乱発した.このようにしても3番と4番の効率テストには合格していませんが、このコードさえなければ1番と2番の効率テストにも合格できません.

    ΄コード（エラーコード）


    ->すべての正確性テストは合格しましたが、効率テスト3,4は未合格のコードです.
    def solution(phone_book):
    answer = True
    data = dict()
    
    # 1. 리스트 phone_book을 정렬한다.
    phone_book.sort()
    # 2. 새로운 딕셔너리에 값을 넣는다.
    for phone_number in phone_book:
        # 이미 딕셔너리에 첫글자가 있다면
        if phone_number[0] in data:
            data[phone_number[0]].append(phone_number)
        else:
            data[phone_number[0]] = [phone_number]
            
    # 3. data의 key별로 values를 순회한다.
    for num in data:
        if answer == False:
            break
        p_numbers = data[num]
        # 앞쪽에 있는 수 -> index i
        for i in range(0,len(p_numbers) - 1):
            if answer == False:
                break
            # 뒤쪽에 있는 수 -> index j
            for j in range(i + 1, len(p_numbers)):
                if p_numbers[i] in p_numbers[j]:
                    answer = False
                    break
    return answer

    他の人のコード->より効率的なコードを参照してください

  • phone bookをソートすると、ある番号のプレフィックスとなるコードが互いに隣接することになる.そのため、前後の番号を比較すれば、正解が得られます.
  • ですが、ハッシュ型は使用しません.
    • def solution(phone_book):
    answer = True

    phone_book.sort()
    for i in range(len(phone_book) - 1):
        l = len(phone_book[i])
        if phone_book[i] == phone_book[i + 1][:l]:
            answer = False    
    return answer

    他者のコード->ハッシュマッピングを使用したコード

  • 海西地図はphone bookの電話番号をすべてキー値に保存します.このときvalueは意味のない値です.
  • phone bookの電話番号をtemp変数に逐字入力し、これまで求めたtempが海図に存在するかどうかを確認します.
    • def solution(phone_book):
    answer = True
    hash_map = {}
    
    # 해시맵에 phone_book에 있는 전화번호를 모두 key값으로 저장한다.
    for phone_number in phone_book:
        hash_map[phone_number] = 1
        
    # phone_book에 있는 전화번호를
    for phone_number in phone_book:
        temp = ""
        # 한글자씩 가져와 
        for number in phone_number:
            # temp 변수에 붙여가면서
            temp += number
            # 현재까지 구한 temp가 해시맵에 존재하는지 검사한다.
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer
    整列挿入
    [プログラマ]2つの整数の和