[백준][Java] 10815번 숫자 카드 (이진탐색)

수행 시간 1328ms -> 928ms (이진탐색 -> 해시셋)

이게 .. 이진탐색은 Arrays.sort() 메서드로 정렬을 한번 해줘야 하고

원소 1개의 탐색 시간이 o(log2(N))이기 때문에 HashSet보다 더 오래 걸리는듯

 

HashSet은 정렬 필요 없고 탐색 시간 o(1)임

 

근데 시간이 dramatically하게 차이나는 것은 아닌듯..

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        String[] str = br.readLine().split(" ");
        Set<Integer> numSet = new HashSet<>();
        for(int i=0; i<N; i++) 
            numSet.add(stoi(str[i]));
        
        int M = stoi(br.readLine());
        str = br.readLine().split(" ");
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            if( numSet.contains(stoi(str[i])) )
                sb.append("1 ");
            else
                sb.append("0 ");
        }
        
        System.out.println(sb.toString());
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

 

 

 

 

이진 탐색으로 해결한 것.. 문제 태그에 관계 없이 가장 최적(메모리, 수행시간 Min)의 해결법을 찾으려는 노력을 해봐야겠다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    private static boolean isExist(int[] num, int card) {
        int left = 0;
        int right = num.length-1;
        
        while(left<=right) {
            int mid = (left + right)/2;
            
            if(num[mid]==card) {
                return true;
            }
            else if(num[mid]<card) {
                left = mid+1;
            }
            else {
                right = mid-1;
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] num = new int[N];
        for(int i=0; i<N; i++) 
            num[i] = stoi(str[i]);
        
        Arrays.sort(num);
        
        int M = stoi(br.readLine());
        str = br.readLine().split(" ");
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++) {
            if( isExist(num, stoi(str[i])) )
                sb.append("1 ");
            else
                sb.append("0 ");
        }
        
        System.out.println(sb.toString());
        
        
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}