備忘録No.2「ArrayListとHashSetで検索履歴を作る」[Java]

はじめに

paizaのスキルチェック入門編で苦戦したので記録。

やりたい事

1.任意の文字数の文字列を複数入力し、リストに持たせる。
2.その際、入力した文字列がすでにリストに存在していたら、以前の文字列を削除し、新しく追加する。
3.一番新しく入力されたものから順に上から出力する。

コード1

        Scanner sc = new Scanner(System.in);
        List<String> words = new ArrayList<>();
        while(sc.hasNext()) {
            String s = sc.nextLine();
            if(words.contains(s)) {//すでにリストにあるか調べ、存在していたら削除する
                words.remove(s);
            }
            words.add(0, s);//入力された文字列をリストの先頭に加える
        }

        for(String word : words) {
            System.out.println(word);
        }

コード１の問題点

・ArrayListは、remove()やadd()で値を増減させると、格納されている全ての値をずらさなければいけない為、処理に時間がかかる。
・ArrayListのcontains()も、リスト内の全ての値を検索する為、格納されている値が多いほど、処理時間が長くなる。

解決策

・文字列の検索にHashSetを使う。→ 要素をハッシュ値に変換して検索に使うことができ、素早く値を発見できる。

コード2

入力された文字列は全てリストに追加し、HashSetを使って、重複しているものは表示しないようにする。（実際に削除するのではなく、無かったことにする)

        Scanner sc = new Scanner(System.in);

        List<String> words = new ArrayList<>();
        while(sc.hasNext()) {
            String s = sc.nextLine();
            words.add(s);
        }

        Collections.reverse(words);//新しく入力されたものから出力する為にリストを反転

        Set<String> usedWords = new HashSet<>();//リスト内の文字列の重複の判定に使うHashSet

        for(String word : words) {
            if(!usedWords.contains(word)){//すでにusedWordに追加されているか(重複しているか)を判定し、していなかったら表示
                System.out.println(word);
            }
            usedWords.add(word);
        }