이분탐색 - 백준1920 수 찾기

첫번째 풀이는 HashSet을 사용하는 것이다.
HashSet은 HashMap을 이용하므로 Sorting하지 않고도 빠르게 Search가 가능하다.
사용한 HashSet 메서드

• add()
• contains()

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));

        HashSet<Integer> hashSet = new HashSet<>();
        
        int arrN = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < arrN; i++) {
            hashSet.add(Integer.parseInt(st.nextToken()));
        }
        int toSearchN = Integer.parseInt(br.readLine());
        int[] toSearch = new int[toSearchN];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < toSearchN; i++){
            toSearch[i] = Integer.parseInt(st.nextToken());
        }
        
        for(int i = 0; i < toSearchN; i++){
            int x = toSearch[i];
            boolean found = hashSet.contains(x);
            if(found){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
        }
    }
}

두번째 풀이는 정렬 후, 이분탐색으로 찾는 것이다.
주의 및 참고

• 이분탐색 코드를 재귀함수로 작성할 시 StackOverflow가 일어난다.
• 배열은 Arrays.sort(), 리스트는 Collections.sort()로 정렬할 수 있다.
• 문제와 크게 상관은 없지만 index사용이 중요한 경우는 배열,
  contains()등과 같은 자료구조의 기능을 활용하는 경우는 리스트를 사용한다.

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 firstN = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[firstN];
        for(int i = 0; i < firstN; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

        //sorting
        Arrays.sort(arr);

        //binary search
        for(int i = 0; i < secondN; i++){
            int x = toSearch[i];

            int left = 0;
            int right = arr.length-1;

            int answer = -1;
            while(true){
                if(left > right){
                    answer = 0;
                    break;
                }
                int mid = (left + right)/2;
                if(arr[mid] == x){
                    answer = 1;
                    break;
                }
                if(arr[mid] < x){
                    left = mid+1;
                }
                if(arr[mid] > x){
                    right = mid-1;
                }
            }
            System.out.println(answer);
        }
    }
}