[伯俊]1920号-Javaを探して

1920番問題の検索

質問する

N個の整数A[1]、A[2]、...、およびA[N]が与えられた場合、Xという整数が存在するか否かを判定するプログラムを作成してください.

入力

第1行は自然数N(1≦N≦100000)を与える.次の行には、N個の整数A[1],A[2],...,A[N]が与えられる.次の行はM(1≦M≦100000)を与える.次の行はM個の数を与え、これらの数がAに存在するかどうかを見つければよい.すべての整数の範囲は、231未満の-231以上です.

しゅつりょく

M行に答えを出力します.存在する場合は1を出力し、存在しない場合は0を出力します.

入力例1

5
4 1 5 2 3
5
1 3 7 9 5

サンプル出力1

1
1
0
0
1

マイコード

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		// 입력에 사용할 BufferedReader 선언, 초기화    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 출력에 사용할 BufferedWriter 선언, 초기화        
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// 한 줄 씩 입력 받은 내용을 나눠 줄 StringTokenizer 선언        
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		// 입력 받은 값을 담을 배열 선언        	
		int[] arrN = new int[n];
		
		// n개의 정수를 입력 받고 그것을 st에 저장        
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			// n개의 정수를 하나씩 배열에 담음        
			arrN[i] = Integer.parseInt(st.nextToken());
		}
		
		int m = Integer.parseInt(br.readLine());
		// m개의 정수를 입력 받고 그것을 st에 저장        
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < m; i++) {
			// 위에서 저장한 arrN 배열 안에 정수의 값이 있다면 1을 출력  
			// 값 확인을 위한 contain 메소드 사용            
			if(contain(Integer.parseInt(st.nextToken()), arrN)) {
				bw.write(1 + "\n");
			// 없다면 0을 출력                
			} else {
				bw.write(0 + "\n");
			}
		}
		br.close();
		bw.close();
	}
	
	// 배열 내에 정수 값이 있는지 확인하는 contain 메소드 생성    
	public static boolean contain(int num, int[] arr) {
		for(int i : arr) {
			if(i == num) return true;
		}
		return false;
	}
}

悩みの部分

初めてコードを記述する場合は、ArrayListを用いてn個の整数の値を格納し、contains関数を用いて整数が存在するか否かをチェックし、出力するように解く.

しかしcontains関数の使用では時間オーバーヘッドが大きいためタイムアウトが発生した.

は、配列を用いてコードを修正する.

他人のコード

public class Main{
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		HashMap<String, String> h = new HashMap<>();
		
		int n = Integer.parseInt(br.readLine());
		
		for(String temp : br.readLine().split(" ")) {
			h.put(temp, temp);
		}
		
		int m = Integer.parseInt(br.readLine());
		
		for(String temp : br.readLine().split(" ")) {
			if(h.get(temp) != null) {
				sb.append('1').append('\n');
			}
			else {
				sb.append('0').append('\n');
			}
		}
		
		System.out.println(sb);
	}
}

コード解釈

は、大量のデータを取得する際に、高速ハッシュマッピングを使用する.

キーと値に値が含まれており、getメソッドを使用してキーを検索する場合、値がない場合は0を出力し、ある場合は1を出力します.