백준 1920 이분탐색 수 찾기

문제 링크

문제 풀이

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

사실 지문을 읽고 나서 문제를 이해하지 못했다. 물론 인풋 아웃풋을 보고도 이해하지 못했다.

<인풋>

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

<아웃풋>

1
1
0
0
1

첫 째줄 부터 둘째 줄까지는 int[] A에 대한 인풋이고
셋 째줄 부터 넷째 줄까지는 target에 대한 인풋이다.
target을 훑으며 intp[] A안에 있는지 아웃풋으로 순서대로 출력하면 된다.

이분탐색

이진 탐색은 O(n)이 log(n)으로 일정 크기 이상으로 넘어가면 극적으로 효율적으로 변한다.
이진 탐색은 탐색해야할 대상의 범위를 반으로 나눠 탐색 범위를 효과적으로 줄여간다. 쉽게 생각하면 up down 게임을 할 때를 생각하면 편하다. 주의해야 할 것은 이진탐색의 대상은 sort를 해야한다는 것이다.
이진 탐색을 저번에 공부했었는데, 코드로 구현한 적은 처음이었다. 하지만 원리를 알고 나면 그렇게 어려운 것은 아닌 것 같다. 재귀를 사용해 중간지점과 구분하여 탐색 범위를 줄여나가면 된다.
해쉬맵을 사용해서 도 풀 수 있다.

코드

이분탐색

import java.util.*;
public class Main {

    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();
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ;i<m ; i++){
            int tmp = binarySearch(arr, sc.nextInt(), 0, n-1);
            sb.append((tmp==-1? 0:1)+"\n");
        }
        System.out.println(sb);
    }
    static int binarySearch(int[] arr, int target, int start, int end){
        if(start>end) return -1;
        
        int mid = (start+end)/2;
        
        if(arr[mid]==target){
            return mid;
        }else{
            if(target> arr[mid]){
                return binarySearch(arr, target, mid+1, end);
            }else{
                return binarySearch(arr, target, start, mid-1);
            }
        }
    }
}

해시맵 풀이

import java.util.*;

public class Main{
    static HashMap<Integer, Integer> map;
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int n = sc.nextInt();
        map = new HashMap<>();
        for(int i = 0 ; i<n ; i++){
            map.put(sc.nextInt(), 1);
        }
        int m = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for(int i =0 ; i<m; i++){
            int tmp = sc.nextInt();
            int ans = 0;
            if(map.containsKey(tmp)) ans =1;
            sb.append(ans+"\n");
        }
        System.out.println(sb);
    }
}