こんにちわ
グローバルセンス株式会社のskanehiraです。
今回はAOJのBinary Searchを解いてみました。
タイトルを見た時に難しいそうだなぁと思いましたが
案外簡単だった…
問題
要約すると
2行目の数列に4行目の数列の値がいくつ含まれているかを出力しろ
という内容です。
ソース
正直1,3行目の入力は要らないかなぁ…
わざわざスキップする処理を入れたくないので。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
// スキップ
scan.nextLine();
// 検索対象をmapに格納する
Map<String, String> map = new HashMap<String, String>();
for (String num : scan.nextLine().split(" ")) {
map.put(num, "");
}
// スキップ
scan.nextLine();
// 検索対象が存在する場合はカウントする
int count = 0;
for (String num : scan.nextLine().split(" ")) {
if (map.containsKey(num)) {
count++;
}
}
System.out.println(count);
}
}
}
解き方
for (int i : targetNums) {
for (int j : nums) {
if (i = j) count++;
}
}
2行目と4行目を配列に格納して
ぐるぐる回しながら比較すれば行けるかなぁと思ったのですが
for文を2重にするのは効率悪いなので
mapを使うことにしました。
検索対象をmapのキーにしてキーチェックをした方が処理が早いはず!(検証はしていないが)
他にもっと効率良いやり方ないかな…