[BOJ] 1920: 수 찾기(JAVA)

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

1920번: 수 찾기

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

출력

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

예제 입력 1 

5

4 1 5 2 3

5

1 3 7 9 5

예제 출력 1 

1

1

0

0

1

 

---

[문제 풀이]

이분 탐색으로 문제를 해결하면 된다.

N을 입력받고 크기가 N인 정수 배열 A를 선언한다.

A에 입력받은 값을 저장하고 Arrays.sort()를 이용해 값을 정렬한다.

 

binarySearch(int m, int[] A)

1. left = 0, right = A배열의 크기 -1 로 선언

2. left가 right보다 커질 때까지 while문

    2-1. mid = (left+right)/2 로, A 배열에서 탐색할 위치이다.

    2-2. A[mid]가 찾고자 하는 값(m)과 같으면 mid를 return

    2-3. A[mid]가 찾고자 하는 값(m)보다 작으면 left = mid+1; 하고 계속 진행

    2-4. A[mid]가 찾고자 하는 값(m)보다 크면 right = mid-1; 하고 계속 진행

3. while문이 종료되고도 해당 함수가 종료되지 않았다면, 값을 찾지 못한 것이므로 -1을 return

 

return된 값이 0보다 크거나 같으면 해당 원소를 찾은 것이므로 StringBuilder sb에 "1"을 append하고, 그렇지 않으면 "0"을 append한다.

 

찾고자하는 모든 값에 대해 위의 과정이 완료되었으면 sb를 출력한다.

 

[코드]

import java.util.*;

   public class Main{
     public static int binarySearch(int m, int[] A) {
        int left=0;
        int right= A.length-1;
     
        while(left<=right) {

            int mid = (left+right)/2;
            if(A[mid]==m) 
                return mid;
            
            else {
                if(A[mid]<m) 
                    left = mid+1;
  
                else 
                    right = mid-1;
            }
        }
        return -1;
   }
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int N = sc.nextInt();
         int[] A = new int[N];
         for(int i=0;i<N;i++)
             A[i] =  sc.nextInt();
    
         Arrays.sort(A);
    
        int M = sc.nextInt();
        StringBuilder sb = new StringBuilder();
    
         for(int i=0;i<M;i++) {
             int m = sc.nextInt();
             
             if(binarySearch(m, A) >=0)
                sb.append("1").append("\n");
             else
                sb.append("0").append("\n"); 
    
         }
    
         System.out.println(sb.toString());  
    }
}