演習課題「検索履歴」
※ この問題は、前回のチャプターの演習課題と同じ問題です。
あなたが利用しているブラウザでは検索ワードの履歴を見ることができません。あなたは検索ワードの履歴を見られないのは不便だと思ったので、検索ワードの履歴を見る機能を自分で作ることにしました。
検索ワードの履歴とは次のように作られます。
* 検索ワード W が以前に入力されたことがある場合：
* 履歴中の W を削除する。
* 履歴の先頭に W を追加する。
* 検索ワード W が以前に入力されたことがない場合：
* 履歴の先頭に W を追加する。
入力例 1 では履歴は
1. candy
2. book
3. apple
になります。
検索ワード W が N 個与えられるので、N 個の検索ワードが与えられた後の履歴を表示するプログラムを書いてください。
期待する出力値
candy
book
apple
演習課題「検索履歴」
※ この問題は、演習1と同じ問題ですが、テストケースが異なります。アルゴリズムを意識して回答しないと、タイムオーバーになるテストケースがございます。
あなたが利用しているブラウザでは検索ワードの履歴を見ることができません。あなたは検索ワードの履歴を見られないのは不便だと思ったので、検索ワードの履歴を見る機能を自分で作ることにしました。
検索ワードの履歴とは次のように作られます。
* 検索ワード W が以前に入力されたことがある場合：
* 履歴中の W を削除する。
* 履歴の先頭に W を追加する。
* 検索ワード W が以前に入力されたことがない場合：
* 履歴の先頭に W を追加する。
検索ワード W が N 個与えられるので、N 個の検索ワードが与えられた後の履歴を表示するプログラムを書いてください。
期待する出力値
candy
book
apple
＃04:実行時間を早くする
前回のチャプターでは、実際に問題を解きました。
このチャプターでは、前回のチャプターのコードをより実行時間の早いものにしていきます。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//検索ワード数を受け取る
int N = sc.nextInt();
//履歴用のArrayListを作成
ArrayList<String> words = new ArrayList<String>();
//次に受け取る検索ワードがある間
while (sc.hasNext()) {
//検索ワードを受け取る
String W = sc.next();
//検索ワードを履歴リストに追加
words.add(W);
}
//リストを反転
Collections.reverse(words);
//HashSetを作成
HashSet<String> usedWords = new HashSet<>();
//出力
for (String word : words) {
//HashSetに入っていなかったら出力
if (!usedWords.contains(word)) {
System.out.println(word);
}
//出力したものは使用済みにする
usedWords.add(word);
}
}
}
// 前回作成したコード
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//検索ワード数を受け取る
int N = sc.nextInt();
//履歴用のArrayListを作成
ArrayList<String> words = new ArrayList<String>();
//次に受け取る検索ワードがある間
while(sc.hasNext()){
//検索ワードを受け取る
String W = sc.next();
//検索ワードがリストに入ってるかどうか
if(words.contains(W)){
//すでに検索されていたとき、そのワードを履歴リストから削除
words.remove(W);
}
//検索ワードを履歴リストに追加
words.add(0,W);
}
//出力
for (String word : words) {
System.out.println(word);
}
}
}
5
book
candy
apple
book
candy
6
apple
book
information
note
pen
pineapple
要素がある規則により数値化し、そこを保存場所とする。
そのため、検索時は配列の要素を1つ1つ探す必要がない。
また、重複も順番も存在できない。
要素 → ある規則による計算 → 数値化 → 保存場所
ハッシュテーブルを用いたセット
宣言
HashSet<型> HS = new HashSet<>();
要素の追加
HS.add(追加したい要素)
要素の削除
HS.remove(削除したい要素)
要素の有無
HS.contains(調べたい要素)
セット内の要素数
HS.size()
検索履歴
下記の問題をプログラミングしてください。
あなたが利用しているブラウザでは検索ワードの履歴を見ることができません。あなたは検索ワードの履歴を見られないのは不便だと思ったので、検索ワードの履歴を見る機能を自分でつくることにしました。
検索ワードの履歴とは次のようにつくられます。
検索ワード W が以前に入力されたことがある場合：
履歴中の W を削除する。
履歴の先頭に W を追加する。
検索ワード W が以前に入力されたことがない場合：
履歴の先頭に W を追加する。
検索ワード W が N 個与えられるので、N 個の検索ワードが与えられた後の履歴を表示するプログラムを書いてください。
入力される値
入力は以下のフォーマットで与えられます。
N
W_1
W_2
...
W_N
1 行目には検索ワードの数を表す整数 N が与えられます。
続く N 行では検索ワード W_i が与えられます。
続く N 行のうちの i 行目 (1 ≦ i ≦ N) には、検索ワード W_i が与えられます。検索ワード W_i は小文字のアルファベット a ~ z のみからなる文字列です。
入力は合計 N + 1 行であり、 最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。
期待する出力
検索ワードを N 個入力した後の検索履歴を出力してください。
出力の最後に改行を入れ、余計な文字、空行を含んではいけません。
条件
すべてのテストケースにおいて、以下の条件をみたします。
1 ≦ N ≦ 100
各 W_i (1 ≦ i ≦ N) に対して、W_iの文字数が20を超えない。
入力例1
5
book
candy
apple
book
candy
出力例1
candy
book
apple
入力例2
6
apple
book
information
note
pen
pineapple
出力例2
pineapple
pen
note
information
book
apple