백준 No.10815 숫자카드- JAVA

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있따. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오

 

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

 

 

 

풀이

첫번쨰로 주어진 숫자 중에 두번쨰로 주어진 숫자가 포함된다면 1을 출력하고 없으면 0을 출력하면 된다. 문제는 쉬웠는데 이상한 곳에서 계속 멈춰있었다... while문에서 else 구문에 빠지고 탈출을 break로 해버리면 for문까지 탈출해버렸기 때문에 최대한 다른 방법으로 해보려 했지만 못하다가 메소드로 분리하니까 바로 해결

이진 탐색으로 문제를 푸는데 시작 인덱스 0부터 주어진 N-1 인덱스를 기준으로 두번쨰 줄에 주어진 배열을 탐색하면된다. 탐색할 떄 for문을 통해 M 배열을 순회하는 for문을 작성하고 그 안에 left ,.right 인덱스를  정해 while 사용해서 탐색하면된다,

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{


    static int arr[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());

        for(int i = 0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int M = Integer.parseInt(br.readLine());
        st= new StringTokenizer(br.readLine());

        Arrays.sort(arr);
        for (int i = 0; i < M; i++) {
            int find = Integer.parseInt(st.nextToken());

            if (result(find,N)) System.out.print(1+" ");
            else System.out.print(0+" ");

        }
    }

    static boolean result(int find,int N){
        int left = 0;
        int right = N-1;

        while(left <= right){

            int midIndex = (right+left)/2;
            int mid = arr[midIndex];

            if(mid < find){
                left = midIndex+1;
            }else if(mid > find){
                right = midIndex-1;
            }else if(find == mid){
                return true;
            }
        }
        return false;
    }
}