(백준/자바) 10815번 문제 : 숫자카드 (HashMap은 속도가 빠르다 !)

10815번: 숫자 카드 (acmicpc.net)

10815번: 숫자 카드

이거를 Arraylist로 작성했는데 시간초과가나서 HashMap으로 바꿨더니 됐다 !!

HashMap은 속도가 빠르다더니 정말 빠른가봐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        Map <Integer,Integer> map = new HashMap<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<N;i++) {
        	map.put( Integer.parseInt(st.nextToken()),0);
        }
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) {
        	if(map.containsKey(Integer.parseInt(st.nextToken())))
        		sb.append(1+" ");
        	else sb.append(0+" ");
        }
        System.out.println(sb);    
    }
}

이렇게 했는데 이진탐색으로 풀어야하는 문제였나보다 ,,,

다시 풀어보자 !

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());

        int arr[] = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0;i<N;i++) {
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
  
        for(int i=0;i<M;i++) {
        	int key = Integer.parseInt(st.nextToken());
        	int start = 0;
            int end = arr.length-1;
        	int ch = 0;
        	while(start<=end) {
        		int mid = (start+end)/2;
        		
        		if(key < arr[mid]) end = mid -1;
        		else if(key >arr[mid]) start = mid + 1;
        		else if(key == arr[mid]) {
        			ch = 1;
        			break;
        		}
        	}
        	if(ch == 0)
        		sb.append(0+" ");
        	else 
            	sb.append(1+" ");
        }
        System.out.println(sb);    
    }
}

간단하게 풀긴했는데 이진탐색이 Map으로 한 것보다 시간 더 걸리는데 ??? ㅡㅡ

위 -> BinartSearch

아래 -> map