백준 1920번 수찾기 [JAVA]

import java.util.Scanner;
import java.util.HashSet;

public class 수찾기해쉬 {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(); //첫번째 case 입력
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<n;i++){
            set.add(sc.nextInt());  //일단 첫번째 case는 HashSet에 담는다
        }

        int m=sc.nextInt(); //두번째 case 입력
        int []arr=new int[m];
        for(int i=0;i<m;i++){
            arr[i]=sc.nextInt(); //두번째 case는 배열에 저장

        }

        int []count=new int[m]; //두번째 case가 HashSet에 있으면 1 아니면 0을 저장하는 배열
        for(int i=0;i<m;i++){
            if(set.contains(arr[i])) //두번째 case가 HashSet에 있으면 1 아니면 0반환
                count[i]=1;
            else
                count[i]=0;
        }
        for(int i=0;i<m;i++){
            System.out.println(count[i]);
        }
    }
}

 

 

첫번째 case와 두번째 case를 둘다 배열에 저장하면 시간복잡도가 오래걸리지만 -> O(N^2)

첫번째 case를 HashSet에 담아놓고 두번째 case만 배열에 저장해서 인덱스로 접근해 HashSet의 요소들과 비교하면 시간복잡도가 더 작아진다. ->O(N)