1920_수 찾기 (JAVA) (C++)

1920번: 수 찾기

[C++]

#include <cstdio>
#include <algorithm> //sort
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int number[n];
    for(int i=0; i<n; i++){
        scanf("%d", &number[i]);
    }
    sort(number, number+n);

    int m;
    scanf("%d", &m);
    int check[m];
    for(int i=0; i<m; i++){
        scanf("%d", &check[i]);
    }

    for(int i=0; i<m; i++){
        bool flag = false;
        int findNum = check[i];

        int mid;
        int start=0, end=n-1;
        while(start<=end){
            mid = (start+end)/2;

            if(findNum > number[mid])
                start = mid+1;
            else if(findNum < number[mid])
                end = mid-1;
            else{
                flag = true;
                break;
            }
        }

        if(flag) printf("1\n");
        else printf("0\n");
    }

    return 0;
}

 

 

 

[JAVA]

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int N;
	static int[] num;
	static int M;

	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); num = new int[N];
		for(int i=0; i<N; i++){
			num[i] = sc.nextInt();
		}
		Arrays.sort(num);

		M = sc.nextInt();
		for(int i=0; i<M; i++){
			int check_num = sc.nextInt();
			check(check_num);
		}

    }

    public static void check(int check_num){
		int left = 0;
		int right = num.length-1;
		int mid = 0;
		boolean flag = false;

		while(left <= right){
			mid = (left+right)/2;
			if(check_num < num[mid]) right=mid-1;
			else if(check_num > num[mid]) left=mid+1;
			else{
				flag = true;
				break;
			}
		}

		if(flag) System.out.println("1");
		else System.out.println("0");
	}
}

 

 

1. 이분탐색은 정렬이 된 상태로 체크해야되기때문에! 입력받은 num[]을 정렬해준다.  : Arrays.sort(num);

 

2. check()함수로 넘어가서 이분탐색!

     이 문제는 찾는값의 위치는 필요없고, num[]에 속하는지만 확인하면되니까 flag변수로 체크만 해서 출력한다.