[백준] 1920 수 찾기 | 이분탐색, 해시 | 실버 Ⅳ | JAVA

시간 복잡도 분석

• 이진 탐색 방법:
  • 배열 정렬: O(Nlog⁡N)
  • 배열 BBB의 각 원소에 대해 이진 탐색: O(Mlog⁡N)
  • 총 시간 복잡도: O((N+M)log⁡N)
• HashSet 방법:
  • HashSet 저장: O(N)
  • 배열 BBB의 각 원소 탐색: O(M)
  • 총 시간 복잡도: O(N+M)

---

⭐ 정답코드

✅ 이진 탐색 이용

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 배열 A 입력
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // 배열 A 정렬
        Arrays.sort(A);

        // 배열 B 입력
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            // 이진 탐색으로 존재 여부 확인
            if (binarySearch(A, target)) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        // 결과 출력
        System.out.print(sb);
    }

    // 이진 탐색 메서드
    private static boolean binarySearch(int[] array, int target) {
        int left = 0, right = array.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (array[mid] == target) {
                return true;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}

✅ HashSet 이용

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 배열 A 입력
        int N = Integer.parseInt(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            set.add(Integer.parseInt(st.nextToken()));
        }

        // 배열 B 입력
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(st.nextToken());
            if (set.contains(target)) {
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }

        // 결과 출력
        System.out.print(sb);
    }
}

🚩 결론

• 이진 탐색 방법은 NNN이 크고 MMM이 상대적으로 작을 때 유리하다.
• HashSet 방법은 평균적으로 더 빠른 탐색을 제공하며, 데이터 크기가 큰 경우에 유리하다.
• 두 방법 모두 시간 복잡도가 효율적이므로 문제의 제약 조건 내에서 동작한다.