문제 설명

정수 배열 A가 주어질 때,
여러 개의 값 X에 대해

배열 A에 존재하는지 여부

를 판단하는 문제이다.

---

입력

첫째 줄

N

배열 크기

둘째 줄

A 배열

셋째 줄

M

넷째 줄

찾을 값들

조건

1 ≤ N, M ≤ 100000

---

출력

각 값에 대해

존재하면 1
없으면 0

---

입력 예시

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

출력 예시

1
1
0
0
1

---

문제 해결 아이디어

이 문제의 핵심은 다음이다.

빠르게 존재 여부 확인

---

가능한 방법

1. 이중 반복 → O(N×M) → 시간초과
2. 정렬 + 이분탐색 → O(N log N + M log N)
3. HashSet → O(N + M)

---

내가 작성한 코드

나는 HashSet을 사용해서 해결했다.

코드

import java.util.*;

class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        Set<Integer> nums = new HashSet<>();

        for(int i = 0; i < N; i++) {
            nums.add(sc.nextInt());
        }

        int M = sc.nextInt();

        int[] result = new int[M];
        int[] A = new int[M];

        for(int i = 0; i < M; i++) {
            A[i] = sc.nextInt();
        }

        for(int i = 0; i < M; i++) {

            if(nums.contains(A[i]))
                result[i] = 1;
            else
                result[i] = 0;

            System.out.println(result[i]);
        }
    }
}

---

강의 코드 (이분 탐색)

배열을 정렬한 뒤
이분 탐색으로 존재 여부를 확인한다.

코드

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static boolean isExist(int[] arr, int x) {

        int l = 0, r = arr.length - 1;

        while (l <= r) {

            int m = (l + r) / 2;

            if (arr[m] < x) l = m + 1;
            else if (arr[m] > x) r = m - 1;
            else return true;
        }

        return false;
    }

    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] arr = new int[N];

        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

        Arrays.sort(arr);

        int M = sc.nextInt();

        while (M-- > 0) {

            int x = sc.nextInt();
            boolean ans = isExist(arr, x);

            System.out.println(ans ? 1 : 0);
        }
    }
}

---

강의 코드 (Set 방식)

코드

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

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < N; i++)
            set.add(sc.nextInt());

        int M = sc.nextInt();

        while (M-- > 0) {

            int x = sc.nextInt();
            System.out.println(set.contains(x) ? 1 : 0);
        }
    }
}

---

내 코드 vs 강의 코드 비교

1. 자료구조 선택

내 코드

HashSet 사용

→ 빠른 탐색 가능

---

강의 코드

방식	특징
이분 탐색	정렬 필요
Set	빠른 탐색

---

2. 시간복잡도 비교

내 코드

O(N + M)

---

강의 코드 (이분 탐색)

O(N log N + M log N)

---

핵심 차이

방식	특징
HashSet	빠르고 간단
이분 탐색	정렬 필요하지만 안정적

---

3. 구현 방식 차이

내 코드

set.contains(x)

→ 한 줄로 해결

---

강의 코드

이분 탐색 직접 구현

→ 알고리즘 이해 필요

---

4. 불필요한 코드

내 코드에서

int[] result
int[] A

→ 사실 필요 없음

---

핵심 개념

1. 존재 여부 탐색 문제

존재 여부 → Set or Binary Search

---

2. HashSet 특징

삽입: O(1)
탐색: O(1)

---

3. 이분 탐색 특징

정렬 필요
탐색: O(log N)

---

시간 복잡도

방식	복잡도
내 코드 (Set)	O(N + M)
강의 코드 (이분탐색)	O(N log N + M log N)

---

정리

이 문제는 단순 구현이 아니라

빠른 탐색 방법 선택

이 핵심이다.

내 코드는 HashSet을 사용하여
가장 효율적인 방식으로 해결했다.

강의에서는

• 이분 탐색
• Set

두 가지 방법을 보여주었다.

핵심 차이는 다음과 같다.

내 코드   → 자료구조 활용
강의 코드 → 알고리즘 구현

즉,

탐색 문제 → Set or Binary Search

라는 패턴을 기억하는 것이 중요하다.