[백준] 2776 암기왕 - 이분탐색(binary search) JAVA

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

2776번: 암기왕

코드설명

이분탐색 문제 혹은 Set을 활용하여 해결할 수 있습니다.

 

 

시간복잡도를 확인해보면,

N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)  으로써 For문을 활용하여 찾을경우 O(N M )의 시간복잡도가 됩니다. 

이것에 T의 범위는 나오지않았지만, T까지 고려한다면 O(T N M )이 됩니다.

 

이분탐색을 활용하여 해결할 경우 시간복잡도는 O(T M log N) 입니다. 

Set은 값을 포함하는지 확인하는 시간복잡도가 O(1) 입니다. 

 

이분탐색과  Set을 활용하여 해결해보겠습니다. 시간복잡도가 Set이 더 빠르지만, 두가지 모두 풀어봅니다.

 

추가로,

출력의 횟수가  M(1 ≤ M ≤ 1,000,000)   * T 이므로 Sysout 을 하는것보다는 StringBuilder를 해야만 시간초과가 나지 않습니다.

 

코드

Hashset을 활용한 코드 ( 시간 1680 ms , 메모리가 285000 KB )

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


public class Main {
	
	public static int T, N, M;
	public static HashSet<Integer> hashset = new HashSet<Integer>();
	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());
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int t=0;t<T;t++) {
            sb = new StringBuilder();
    		
	    	st = new StringTokenizer(br.readLine());
	    	N = Integer.parseInt(st.nextToken());
	    	
	    	hashset = new HashSet<>();
	    	st = new StringTokenizer(br.readLine());
	    	for(int i=0;i<N;i++) {
	    		hashset.add(Integer.parseInt(st.nextToken()));
	    	}
	    	
    		st = new StringTokenizer(br.readLine());
        	M = Integer.parseInt(st.nextToken());
        	
        	st = new StringTokenizer(br.readLine());
        	for(int j=0;j<M;j++) {
        		boolean result = hashset.contains(Integer.parseInt(st.nextToken()));
        		sb.append(result ? 1 : 0).append("\n");
        	}
	        	
        	System.out.print(sb);
    	}

    	
    }
   
}

 

이분탐색을 활용한 코드 ( 시간 2100ms , 메모리 230000 KB )

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


public class Main {
	
	public static int T, N, M;
	public static int[] arr;
	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());
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int t=0;t<T;t++) {
            sb = new StringBuilder();
    		
	    	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 j=0;j<M;j++) {
        		binarySearch(Integer.parseInt(st.nextToken()));
        	}
	        	
        	System.out.print(sb);
    	}

    	
    }
    
    public static void binarySearch(int target) {
    	int start = 0;
    	int end = N - 1;
    	
    	while(start <= end) {
    		int middle = (start + end) / 2;
    		
    		if(arr[middle] == target) {
    			sb.append('1').append("\n");
//    			System.out.println("1");
    			return ;
    		}
    		
    		if(arr[middle] < target) {
    			start = middle + 1;
    		}else {  // while(start <= end) 이기에 end를 더 작게만들어줘야함
    			end = middle - 1;
    		}
    		
    	}
    	sb.append('0').append("\n");
//		System.out.println("0");
    	
    	
    }
}

 

 

추가정보

Set의 시간복잡도 

add         :   O(1)
contains    :   O(1)
next        :   o(h/n) h는 테이블 용량



ArrayList의 시간복잡도

add             : O(1)
remove          : O(n)
get             : O(1)
Contains        : O(n)
iterator.remove : O(n)



LinkedList의 시간복잡도

add             : O(1)
remove          : O(1)
get             : O(n)
Contains        : O(n)
iterator.remove : O(1)