백준 (BOJ) 10815 숫자 카드 java

 

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

10815번: 숫자 카드

 

이분 탐색의 대표적(?) 문제.

 

개수를 나타내는 의미 없는 값 1을 넣고 해시맵도 한 번 써보았다.

 

 

 

 

 

이분 탐색

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

public class Main {
    static int N;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        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);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<M; ++i){
            int key = Integer.parseInt(st.nextToken());

            // binary search
            sb.append(search(key)).append(" ");
        }

        System.out.print(sb);
    }

    static int search(int key){
        int l=0, h=N-1;

        int mid;
        while(l <= h){
            mid = (l+h) >> 1;
            if(arr[mid] < key){
                l = mid + 1;
            }else if(arr[mid] > key){
                h = mid - 1;
            }else{
                return 1;
            }
        }
        return 0;
    }
}

 

 

 

 

 

 

해시맵

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; ++i){
            int key = Integer.parseInt(st.nextToken());
            map.put(key, 1);
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; ++i){
            int key = Integer.parseInt(st.nextToken());
            if(map.containsKey(key)){
                sb.append("1 ");
            }else{
                sb.append("0 ");
            }
        }

        System.out.print(sb);


    }
}

 

 

속도는 해시가 더 빠르다.