[Algorithm/Java] 백준 1920번 - 수 찾기

---

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

---

📌 문제

문제 유형

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

문제 설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입출력 예시

• 입력

  • 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.
  • 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.
  • 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
    
    

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

• 출력

  • M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
    
    

  1
  1
  0
  0
  1
  

🔍 문제 풀이

방법 1: HashSet 사용

처음에는 HashSet을 활용하여 접근하였다.

배열 A의 모든 원소를 집합(Set)에 저장한 후, contains() 메서드를 통해 주어진 수가 존재하는지 여부를 확인하였다.

이 방식은 내부적으로 해시 테이블을 이용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다.

시간복잡도: O(N + M)

방법 2: 이분 탐색 (Binary Search)

이후에는 정렬된 배열을 기반으로 하는 이분 탐색으로 다시 풀어봤다.

배열 A를 오름차순 정렬 한 후, M개의 수 각각에 대해 이분 탐색을 수행하여 존재 여부를 판단한다.

시간복잡도: O(N log N + M log N)

방법 3: Arrays.binarySearch() 메서드 사용

직접 이분 탐색을 구현하는 대신, Java에서 제공하는 Arrays.binarySearch() 메서드를 활용할 수도 있다.

이 메서드는 배열이 정렬되어 있다는 전제 하에, 원하는 값의 존재 여부를 간단하게 확인할 수 있다.

• Arrays.binarySearch(arr, key)
  • 존재하면 해당 인덱스(0 이상) 반환,
  • 존재하지 않으면 음수(삽입 위치 - 1) 반환

방법	정렬 필요 여부	시간복잡도	장점	단점
HashSet	x	O(N + M)	매우 빠르고 간단한 구현	메모리 사용량 큼
직접 구현한 이분 탐색	o	O(N log N + M log N)	안정적인 탐색 성능	코드 길고 정렬 필요
Arrays.binarySearch	o	O(N log N + M log N)	가장 간결한 코드	배열만 지원, 정렬 필요

💻 전체 코드

총 세 가지 방법으로 풀어봤다.

HashSet 사용

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

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

        int n = Integer.parseInt(br.readLine());
        Set<Integer> set = new HashSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            set.add(Integer.parseInt(st.nextToken()));
        }


        int m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        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).append("\n");
            }else{
                sb.append(0).append("\n");
            }
        }
        System.out.println(sb);
    }
}

이분 탐색

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

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

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<nums.length; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums); // 이분 탐색 전에 정렬 필수

        int m = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());

            if(binarySearch(nums, target) >= 0){
                sb.append(1).append("\n");
            }else{
                sb.append(0).append("\n");
            }
        }
        System.out.println(sb);
    }

    public static int binarySearch(int[] arr, int key){
        int low = 0;
        int high = arr.length-1;

        while (low <= high){
            int mid = (low + high) / 2; // 중간 위치

            if(key < arr[mid]){
                high = mid - 1; // key가 더 작으면 왼쪽 탐색
            } else if(key > arr[mid]){
                low = mid + 1; // key가 더 크면 오른쪽 탐색
            } else{
                return  mid; // key를 찾으면 해당 인덱스 반환
            }
        }
        return -1; // key를 찾지 못했을 경우
    }
}

Arrays.binarySearch() 메서드 사용

Arrays.binarySearch(arr, key)

• key가 존재하면 해당 인덱스를 반환 (0 이상)
• 존재하지 않으면 음수((삽입위치 - 1) 형태) 반환

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

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr); // 이분 탐색 전에 정렬 필수

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            // binarySearch: 값이 존재하면 해당 인덱스(0 이상), 없으면 음수 반환
            sb.append(Arrays.binarySearch(arr, target) >= 0 ? "1\n" : "0\n");
        }

        System.out.print(sb);
    }
}