[백준] 10816번 - 숫자 카드 2 (JAVA)

1. 배열을 이용한 방법

 

배열 + 이진탐색 (상위 탐색, 하위 탐색) 사용

1. 배열을 정렬

2. 정렬된 배열의 상위 부터 탐색 하여 나온 인덱스 와 하위 부터 탐색하여 나온 인덱스를 이용하여 숫자의 개수 도출

import java.util.*;
import java.io.*;

class Main {
    static int N, M;

    public static int lowerBound(ArrayList<Integer> array, int target){
        int lo = 0, hi = array.size(), mid;
        
        while (lo < hi) {
            mid = (lo + hi) / 2;

            if (target <= array.get(mid)){
                hi = mid;
            }
            else{
                lo = mid + 1;
            }
        }

        return lo;
    }

    public static int upperBound(ArrayList<Integer> array, int target){
        int lo = 0, hi = array.size(), mid;

        while (lo < hi){
            mid = (lo + hi) / 2;

            // 상위 탐색 target의 idx + 1을 발견하기 위함
            if (target < array.get(mid)){
                hi = mid;
            }
            else{
                lo = mid + 1;
            }
        }

        return lo;
    }

    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        ArrayList<Integer> arr = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr.add(Integer.parseInt(st.nextToken()));
        }

        M = Integer.parseInt(br.readLine());

        ArrayList<Integer> target = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            target.add(Integer.parseInt(st.nextToken()));
        }

        // 1. 이진 탐색하고자 하는 배열 정렬하기
        Collections.sort(arr);

        // 2. 상위 탐색 방법, 하위 탐색 방법을 이용하여 개수 출력
        for(int i=0; i<M; i++){
            bw.write(String.valueOf( upperBound(arr, target.get(i)) - lowerBound(arr, target.get(i)) ) + " ");
        }
        bw.flush();
        
        bw.close();
        br.close();
    }
}

---

2. 해시를 이용한 방법

 

HashMap을 사용.

key : 숫자

value : 숫자가 호명된 횟수

N개의 데이터를 통해 저장한 후,

M번의 쿼리문을 HashMap을 통해 value 반환

// 10816번 - 숫자 카드 2 
// 해시를 사용한 풀이
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1. N개의 정보를 hash에 반영
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> hash = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            int num = Integer.parseInt(st.nextToken());
            
            // 기존에 입력되지 않았던 숫자
            if (hash.getOrDefault(num , 0) == 0){
                hash.put(num, 1);
            } else {
                hash.put(num, hash.get(num) + 1);
            }
        }

        // 2. M개의 쿼리를 해시를 통해 출력
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            int num = Integer.parseInt(st.nextToken());
            bw.write(hash.getOrDefault(num, 0) + " ");
        }
        bw.write("\n");

        bw.flush();
        bw.close();
        br.close();
    }
}