백준 1920 ( Java )

수 찾기

 

N 개의 수를 입력받고 M개의 숫자가 주어졌을 때 해당 숫자가 N 개의 숫자들 중에 존재하는지 판별하는 문제.

 

 

문제 풀이

 

N 과 M의 범위가 1 이상 100,000이다. 그러므로 선형 검색(순차 검색)으로 코드를 짜면 시간제한에 걸릴 확률이 높다.

 

정수를 찾을때는 이분 탐색 (binary search) 알고리즘을 적용하여 검색을 하자.

 

 

그리고 모든 정수는 -2^31 보다 크거나 같고 2^31보다 작다는 제한이 있다. 

 

int 자료형의 범위는 -2^31 -1 ~  2^31 - 1 이므로  음수 부분에서 걸린다. 그러므로 자료형을 long 형으로 해주자.

 

 

 

 

이분 탐색은 정렬된 배열에서 가능하므로 입력받은 N 개의 정수를 배열로 받아 정렬시키는 일부터 한다.

 

import java.util.Arrays; 

 

를 추가하여 Arrays.sort()를 사용 가능하도록 한다.

 

 Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Long A[] = new Long[n];
for (int i = 0; i < n ; i++)
A[i] = sc.nextLong();
 
Arrays.sort(A);

 

M 개의 정수를 받아 배열 안에 존재하는지 판별하는 메서드를 만든다.

 

 public static int binarySearch(Long [] A , long x) {
    int left = 0;
    int right = A.length - 1;
    int mid = 0;
 
    while (left <= right) {
      mid = (left + right) / 2;
 
      if ( A[mid] < x ) {
        left = mid + 1;
      }
      else if ( x < A[mid]) {
        right = mid - 1;
      }
      else if ( x == A[mid]) {
        return 1;
      }
    }
    return 0;
  }

 

 

 

위 코드는 이분 탐색을 적용한 검색 메소드이다.

 

left, right는 다음에 검색을 시작할 첫 번째 인덱스와 마지막 인덱스를 저장하는 변수이다.

 

매번 left와 right의 중간값을 계산하고 찾으려는 숫자가 배열에서 인덱스 mid인 값보다 크면 left를 mid +1로, 작으면

 

right를 mid - 1로 하여 left 가 right보다 커지거나 찾으려는 숫자와 배열에서 인덱스 mid인 값이 동일할 때까지 반복한다.

 

이 방식을 적용하면 검색 시간 복잡도를 O(logN)으로 줄일 수 있다.

 

 

코드

 

 

import java.util.Scanner;
import java.util.Arrays;
 
public class Main {
  public static void main(String [] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Long A[] = new Long[n];
    for (int i = 0; i < n ; i++)
      A[i] = sc.nextLong();
 
    Arrays.sort(A);
    int m = sc.nextInt();
    for (int i = 0; i < m ; i++) {
      long temp = sc.nextLong();
      System.out.println(binarySearch(A, temp));
    }
  }
 
  public static int binarySearch(Long [] A , long x) {
    int left = 0;
    int right = A.length - 1;
    int mid = 0;
 
    while (left <= right) {
      mid = (left + right) / 2;
 
      if ( A[mid] < x ) {
        left = mid + 1;
      }
      else if ( x < A[mid]) {
        right = mid - 1;
      }
      else if ( x == A[mid]) {
        return 1;
      }
    }
    return 0;
  }
}