백준 10815: 숫자 카드(JAVA)

ArrayList의 contains는 타임아웃 발생

*ArrayList의 contians는 시간복잡도: O(n)

 

대신 HashSet을 사용하였다.

*HashSet의 contains는 시간복잡도: O(1)

 

시간을 단축시키기 위해 StringBuilder를 이용하여 출력하였다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		int N, M;
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		HashSet<Integer> arr = new HashSet<>();
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<N; i++)
			arr.add(sc.nextInt());

		M = sc.nextInt();
		for(int i=0; i<M; i++) {
			int n = sc.nextInt();
			if(arr.contains(n))
				sb.append("1 ");
			else
				sb.append("0 ");
		}
		
		System.out.println(sb);
		sc.close();
	}
}