1. ホーム
  2. java

[解決済み] hackerrankで私のコードに "terminated due to timeout "エラーが発生するのはなぜですか?

2022-02-02 06:41:51

質問

特定のテストケースに限ってコードを実行すると、「タイムアウトエラーで終了しました」と表示されます。他のテストケースでは正常にコンパイルできたのに。どなたか、この件に関して助けていただけませんか?

リンク https://www.hackerrank.com/challenges/phone-book

問題提起:

人の名前と電話番号からなる電話帳が渡される。その後、ある人の名前がクエリとして渡される。各クエリに対して、その人物の電話番号を表示せよ。

入力フォーマット :

最初の行は、電話帳の登録件数を示す整数である。各エントリーは、名前とそれに対応する電話番号の2行で構成されています。

この後、いくつかの問合せがあります。各クエリには人名が含まれます。ファイルの終わりまでクエリーを読みます。

制約事項

1<=n<=100000

1<=Query<=100000

人名は小文字の英字のみからなり、「first-name last-name」または「first-name」の形式であることがあります。電話番号は、先頭のゼロを除いたちょうど8桁の数字で構成されています。

出力形式:

各ケースについて、電話帳にその人の項目がない場合は、"Not found"と表示します。そうでなければ、その人の名前と電話番号を表示する。正確な書式はサンプル出力を参照してください。

問題を簡単にするために、エディタにコードの一部を用意しました。そのコードを完成させるか、完全に自分で書くかのどちらかです。

私のコードは以下の通りです。

import java.util.*;
import java.io.*;

class Solution
{
 public static void main(String []args)
 {
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  ArrayList<String> name = new ArrayList<String>();
  int[] phone = new int[100000];

  for(int i=0;i<n;i++)
  {
   name.add(in.nextLine());
   phone[i]=in.nextInt();
   in.nextLine();
  }

  while(in.hasNext())
  {
   String s=in.nextLine();
   int a=name.indexOf(s);

   if(a>=0)
   {
    System.out.println(s + "=" + phone[a] );
   }
   else
   {
    System.out.println("Not found");
   }
  }
 }
}

PS:これは私のフォーラムでの最初の質問です。私はjavaを学んでいるアマチュアです。私は質問をするための多くのルールのいずれかに違反した場合は申し訳ありません:( . 私を修正し、私は良い方法でここにコミュニティに貢献するのに役立ちますしてください:)

どのように解決するのですか?

このロジックの問題は、このロジックが ArrayList これはシーケンシャルな構造です。リスト内の検索は順次行われ、大規模なテストケースでは名前リストの検索に時間がかかりすぎてしまいます。

ハッシュマップは、キーと値のペアでデータを保持し、ハッシュ化されているため検索が高速なので、電話帳の例にはより適しています。

以下は、HashMapを使って実装したバージョンです。

   Map<String,Integer> phonebook = new HashMap<>();
  Scanner in = new Scanner(System.in);
  int n=in.nextInt();
  in.nextLine();
  for(int i=0;i<n;i++)
  {
     String name=in.nextLine();
     int phone=in.nextInt();
     in.nextLine();
      phonebook.put(name,phone);
  }
  while(in.hasNext())
  {
     String s=in.nextLine();
     Integer phone = phonebook.get(s);
     if(phone==null){
         System.out.println("Not found");
     } else {
         System.out.println(s+"="+phone);
     }
  }

これで説明できるといいのですが。