HashSet

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

package class2;

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

public class 수찾기_1_1920 {
    public static void main(String[] args) {
        // Scanner 객체를 생성하여 사용자로부터 입력을 받는다.
        Scanner sc = new Scanner(System.in);

        // 첫 번째 입력으로 정수 n을 받아서 저장한다.
        int n = sc.nextInt();

        // HashSet 객체를 생성하여 n개의 정수를 저장한다. HashSet은 중복을 허용하지 않는다.
        // 또한 HashSet의 contains 메서드는 일반적으로 O(1)의 시간 복잡도를 가지므로 특정 요소의 존재 여부를 빠르게 확인할 수 있다.
        Set<Integer> N = new HashSet<>();
        for (int i = 0; i < n; i++) {
            N.add(sc.nextInt());
        }

        // 두 번째 입력으로 정수 m을 받아서 저장한다.
        int m = sc.nextInt();

        // 결과를 저장할 배열 ans를 선언한다. 배열의 초기값은 모두 0이다.
        int[] ans = new int[m];

        // m개의 정수를 입력받아서 해당 정수가 HashSet에 존재하는지 확인한다.
        // 존재한다면 ans 배열의 해당 인덱스 위치의 값을 1로 변경한다.
        for (int i = 0; i < m; i++) {
            if (N.contains(sc.nextInt())) {
                ans[i] = 1;
            }
        }

        // ans 배열의 값을 모두 출력한다. 해당 위치의 숫자가 N 집합에 존재하면 1, 그렇지 않으면 0을 출력한다.
        for (int value : ans) {
            System.out.println(value);
        }
    }
}

HashSet 객체를 생성하여 n개의 정수를 저장한다. HashSet은 중복을 허용하지 않는다.
또한 HashSet의 contains 메서드는 일반적으로 O(1)의 시간 복잡도를 가지므로 특정 요소의 존재 여부를 빠르게 확인할 수 있다.

이 부분을 통해 HashSet을 사용하면 존재 여부를 더욱 빠르게 알 수 있다.