BOJ10816 숫자카드2

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

10816번: 숫자 카드 2

 

Map 이용

import java.util.*;
import java.io.*;
public class Main
{

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		HashMap<Integer,Integer> hashmap = new HashMap();
		
		int n = Integer.valueOf(br.readLine());
	    String[] input1 = br.readLine().split(" ");
	    int[] num1 = new int[n];
	   
	    int m = Integer.valueOf(br.readLine());
	    String[] input2 = br.readLine().split(" ");
	
		
		
		for(int i=0;i<n;i++){
		    hashmap.put(Integer.valueOf(input1[i]),hashmap.getOrDefault(Integer.valueOf(input1[i]),0)+1);
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<m;i++){
		    int num=Integer.valueOf(input2[i]);
		    sb.append(hashmap.getOrDefault(Integer.valueOf(num),0));
		    sb.append(" ");
		}

    	

		
		System.out.println(sb.toString());
		
		
		
		
	}
}

 

이분탐색 이용

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static int findLowerBoundIndex(int[] arr, int x) {
        // x 이상의 값이 처음으로 나타나는 위치
        int lowerBoundIndex = arr.length;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] < x) l = m + 1;
            else {
                r = m - 1;
                lowerBoundIndex = m;
            }
        }
        return lowerBoundIndex;
    }

    static int findUpperBoundIndex(int[] arr, int x) {
        // x 초과의 값이 처음으로 나타나는 위치
        int upperBoundIndex = arr.length;
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] <= x) l = m + 1;
            else {
                r = m - 1;
                upperBoundIndex = m;
            }
        }
        return upperBoundIndex;
    }

    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] cards = new int[N];
        for (int i = 0; i < N; i++)
            cards[i] = sc.nextInt();

        Arrays.sort(cards);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int M = sc.nextInt();
        while (M-- > 0) {
            int x = sc.nextInt();
            int lowerBoundIndex = findLowerBoundIndex(cards, x);
            int upperBoundIndex = findUpperBoundIndex(cards, x);
            bw.write(upperBoundIndex - lowerBoundIndex + " ");
        }
        bw.write("\n");
        bw.flush();
    }
}