[java] 백준 알고리즘 10815번 숫자카드 풀이 소스(이분 탐색)

이분탐색의 문제이다.

문제푸는 원리는 백준 1920번과 동일해서 다른 설명을 할 필요는 없을 것 같다. (백준 1920 풀이 참고)

단지 백준 1920번 문제와 다른 점이라면 찾는 숫자가 음수가 존재하는 것이지만,

결국 특정한 수를 찾는다는 것에는 다름이 없다.

소스는 아래와 같다.

public class Baekjoon10815 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); // 자연수 N
        String[] beforeAArray = br.readLine().split(" "); // 스트링 배열로 받아지는 특징 때문에 인트배열 담기 전에 생성
        int[] aArray = new int[n];
        
        /* 스트링 배열로 들어온 문자를 인트 배열로 바꿔줌 */
        for(int i=0; i< beforeAArray.length; i++){
            aArray[i] = Integer.parseInt(beforeAArray[i]);
        }
        
        /* 이진탐색을 위한 오름차순으로 정렬 */
        Arrays.sort(aArray);
        
        int m = Integer.parseInt(br.readLine()); // M개의 수
        String[] beforeComArray = br.readLine().split(" ");
        int[] compareArray = new int[m];
        
        /* 스트링 배열로 들어온 문자를 인트 배열로 바꿔줌 */
        for(int j=0; j<beforeComArray.length; j++){
            compareArray[j] = Integer.parseInt(beforeComArray[j]); // 주어질 수에 대한 배열
        }
        
        for(int i =0; i<compareArray.length; i++){ // 지금부터 주어진 수가 aArray 배열에 담긴 수와 일치하는지 반복문을 통해 찾을 것이다.
            int flag = 0;
            
            /* max와 min을 밖에다 선언해주면 while문이 돌지 않는다.(max, min 값을 계속 초기화 해주어야 반복함)*/
            int max = n;
            int min = 0;
            int middle;
            
            while(max - min > 1){
                middle = (min+max)/2;
                
                //while문 로직상 배열의 0번째 값은 확인이 불가능해서 강제로 삽입.
                if(compareArray[i] == aArray[0]){
                    flag = 1;
                    break;
                }
                
                if(compareArray[i] == aArray[middle]){
                    flag = 1;
                    break;
                }
                if(compareArray[i] > aArray[middle]){
                    min = middle;
                }else if(compareArray[i] < aArray[middle]){
                    max = middle;
                }
                
            }
            System.out.print(flag+" ");
            
        }
    }
}