[백준 10815] 숫자 카드 (C++/Java)

이진탐색을 이용하여 풀면 된다.

 

#include<cstdio>
#include<algorithm>
int arr1[500002];
int arr2[500002];
int binary_s(int *ar, int len, int target) {
    int first=0;
    int last=len-1;
    int mid=0;
    
    while(first<=last) {
        mid=(first+last)/2;
        if(ar[mid]==target) return 1;
        else {
            if(ar[mid]>target) last=mid-1;
            else first=mid+1;
        }
    }
    return 0;
}
 
int main(void)
{
    int n,m;
    
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &arr1[i]);
    
    std::sort(arr1, arr1+n);
    
    scanf("%d", &m);
    for(int i=0; i<m; i++) scanf("%d", &arr2[i]);
    
    for(int i=0; i<m; i++)
        printf("%d ", binary_s(arr1,n,arr2[i]));
    
    return 0;
}

 

#include<cstdio>
#include<algorithm>
int arr1[500002];
int arr2[500002];
using namespace std;
int main(void)
{
    int n,m,first,last,mid;
    
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &arr1[i]);
    
    std::sort(arr1, arr1+n);
    
    scanf("%d", &m);
    for(int i=0; i<m; i++) scanf("%d", &arr2[i]);
    
    for(int i=0; i<m; i++) {
        if(binary_search(arr1,arr1+n,arr2[i])==1) printf("1 ");
        else printf("0 ");
    }
    return 0;
}

 

- java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // n 입력받기
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        // 정렬
        Arrays.sort(arr);
 
        // m 입력받기
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
 
        StringBuilder sb = new StringBuilder();
 
        // 
        for(int i=0; i<m; i++){
            int start=0, end = n;
            int target = Integer.parseInt(st.nextToken());
            boolean flag = false;
 
            while(start<=end){
                int mid = (start+end)/2;
 
                if(arr[mid] == target){
                    sb.append("1 ");
                    flag = true;
                    break;
                } else if(arr[mid] < target) {
                    start = mid+1;
                } else
                    end = mid-1;
            }
 
            if(flag == false)
                sb.append("0 ");
        }
 
        System.out.println(sb);
    }
}