[java] 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보다 작다.

출력

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

 

package backjoon_1920;
import java.util.Scanner;
 
public class backjoon_1920 {
    
    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left +1;
        int n2 = right - middle;
        
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];
        
        System.arraycopy(arr,left, leftArr, 0, n1);
        System.arraycopy(arr, middle+1, rightArr, 0, n2);
        
        int i =0, j =0, k=left;
        
        while(i < n1 && j <n2) {
            if(leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i++];
            } else {
                arr[k] = rightArr[j++];
            }
            k++;
        }
        
        while(i <n1) {
            
            arr[k++] = leftArr[i++];
        }
        
        while(j <n2) {
            arr[k++] = rightArr[j++];
        }
    }
    
    public static int binarySearch(int arr[], int key, int low, int high)
    {
        int mid;
        while(low <= high) {
            mid = (low + high)/2;
            if(key == arr[mid]) {
                return mid;
            } 
            else if(key < arr[mid]) {
                return binarySearch(arr, key, low, mid-1);
            }
            else
            {
                return binarySearch(arr, key, mid+1, high);
            }
        }
        return -1;
    }
    
    public static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int middle  = (left + right) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle+1, right);
            merge(arr, left, middle , right);
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n  = in.nextInt();
        int arr1[] = new int[n];
        for(int i =0; i<n; i++)
        {
            arr1[i] = in.nextInt();
        }
        
        mergeSort(arr1, 0, arr1.length-1);
        
        
        int num = in.nextInt();
        int arr2[]  = new int[num];
        for(int i =0; i<num; i++)
        {
            arr2[i] = in.nextInt();
        }
        for(int i = 0; i < arr2.length; i++) {
            int result = binarySearch(arr1, arr2[i], 0, arr1.length - 1);
            if(result != -1) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }
 
        
        
    }
 
}
 

 

풀이

이 문제는 먼저 정렬 후에 그 정렬한 데이터들에 접근하면서 수가 있는지 찾으면 된다. 처음에 어떻게 구현할지 하다가 퀵소트로 구현을 하고자 마음 먹었었다. 근데 퀵소트가 최악의 경우 O(n^2) 가 되기 때문에 무조건 런타임 오류가 날 것 같았다. 그래서 merge sort를 이용해보았다.

또한 정렬된 수에서 값을 찾기 위해서 이진 탐색을 썼는데, 이진 탐색 알고리즘을 까먹은지라 구성하는데 꽤나 오랜시간이 걸렸다. 이진탐색은 재귀하먀수를 통해서 구성했는데 간단하게 mid값과 key값을 확인하여 계속 쪼개고 쪼개면서 값을 찾아나가는 방법이다. mergesort와 binarySerach를 통해 구현할 수 있는 문제였다.