###前提・実現したいこと
このページの問題を解きたいです。
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2949
概要は整数群AとBがあり、AとBに共通して含まれる整数の個数を出力させるというものですが、
UVaの内部でインプットされる整数の数がどうやら膨大らしいので、普通に実装するだけでは時間がかかってしまいます。
そこでHashSetを使えばいいという話を聞いたので、それを使ってやってみたのですが、それでも時間切れになってしまいます。(UVaのサイトの問題は3秒以内で実行できるプログラムでないと跳ねられてしまいます)
入力例は以下の通りです
3 3 //1つ目が整数群Aの要素数、2つ目が整数群Bの要素数 1 //ここから3行分が整数群Aに含まれる要素 2 3 1 //ここから3行分が整数群Bに含まれる要素 2 4 0 0 //0 0が入力されると終了させる ここで別の整数組を入れると、別の要素で続けて実験を行う
以下のソースコードで、まだどこかに無駄をカットできる箇所はありますか?
ちなみにコンパイルはちゃんと通り、出力も正しいものがプリントされています。
###該当のソースコード
java
1import java.util.Set; 2import java.util.HashSet; 3import java.util.Scanner; 4import java.util.InputMismatchException; 5 6class CD { 7 public static void main (String[] args) { 8 Scanner scan = new Scanner(System.in); 9 int output = 0; 10 11 while(scan.hasNext()) { 12 try { 13 int M = scan.nextInt(); 14 int N = scan.nextInt(); 15 if(M==0 && N==0) System.exit(0); 16 17 Set<Integer> cdnum = new HashSet<Integer>(); 18 19 for(int i=0; i<M; i++) 20 cdnum.add(scan.nextInt()); 21 22 for(int i=0; i<N; i++) { 23 if(cdnum.contains(scan.nextInt())) 24 output++; 25 } 26 27 System.out.println(output); 28 output = 0; 29 cdnum.clear(); 30 31 } catch(InputMismatchException e) { 32 System.out.println("Input must be type int."); 33 System.exit(1); 34 } 35 } 36 } 37} 38
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/04/27 06:29