[백준] 10815 숫자 카드 - 이분탐색(binary search) JAVA

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

코드설명

이분탐색 문제입니다.

 

단순히 순회하는것이 아닌, 이분탐색을 사용해야만 시간복잡도를 통과합니다.

 

문제조건을 보면,

상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 

상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수 M(1 ≤ M ≤ 500,000)이 주어진다.

 

단순히, 순회하면서 상근이의 숫자카드인지 확인할경우, M개의 카드가 N개의 카드를 모두 확인해야할 경우가 있습니다.

시간복잡도로는 O(N * M ) = 500,000 * 500,000 = 50,000,000,000 = 500억

 

이분탐색을 활용할경우 O(M * log N) 의 시간복잡도입니다. 

시간복잡도를 구해보면, 500,000 * log 500,000 = 500,000 * 18.931568569324 

 

가장 쉽게 푸는 방식은 HashMap을 사용하는것이 가장 빠를 것 입니다.

코드

StringBuilder 사용

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

public class Main {
	public static int N, M, K = 0;
	public static int[] arr, brr;
	public static int answer = 0;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	Arrays.sort(arr);
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	brr = new int[M];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<M;i++) {
    		brr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	for(int i=0;i<M;i++) {
    		sb.append(binarySearch(0, N - 1, brr[i]) == true ? 1 : 0).append(" ");
    	}
    	System.out.println(sb.toString());
    }
    
    public static boolean binarySearch(int left, int right, int target) {
    	int start = 0;
    	int end = right;
    	
    	while(start <= end) {
    		int middle = (start + end) / 2;
    		
    		if(target == arr[middle]) {
    			return true;
    		}
    		
    		if(arr[middle] < target) {
    			start = middle + 1;
    		}else if(arr[middle] > target) {
    			end = middle - 1;
    		}
    	}
    	
    	return false;
    }
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M;
	public static int[] arr;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	Arrays.sort(arr);
    	
    	st = new StringTokenizer(br.readLine());
    	M = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<M;i++) {
    		answer = 0;
    		find(Integer.parseInt(st.nextToken()));
    		System.out.print(answer+" ");
    	}
    	
    }
    
    public static void find(int target) {
    	int start = 0;
		int	end = N - 1;
		
    	while(start <= end) {
    		int middle = (start + end) / 2;
    		
    		if(target == arr[middle]) {
    			answer = 1;
    			return ;
    		}
    		
    		if(target < arr[middle]) {
    			end = middle - 1;
    		} else if(target >= arr[middle]) {
    			start = middle + 1;
    		}
    		
    	}
    }
}