BOJ 10816번 숫자 카드 2

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

접근

1. 일반적인 이분탐색으로 접근 - 시간초과
2. 해시맵을 사용하여 접근 - 통과 
3. 이분탐색 중 상/하한선 (lower bound, upper bound) 발견 !

 

이론보기

jackpot53.tistory.com/33

이진탐색-상/하한선((lower bound,upper bound)

 

풀이|

해시맵 (HashMAp)

1. 입력받은 수를 해시 맵에 저장
2. 기본값을 0으로 받아오고 1을 더해서 다시 저장
3. target 숫자들을 key로 value값 구해서 출력
 

상/하한선 (lower bound, upper bound)

1. 숫자들을 입력받는다.
2. target 숫자들의 lower bound, upper bound를 구한다.
3. upper bound - lower bound 값을 출력한다.
4. 값이 없는 경우엔 같은 값을 가르키므로 0이 출력됨.
5. 답이 있을 경우엔 답보다 큰값의 인덱스가 upper bound 이고  
답이 처음 나온곳이 lowwer bound 이므로 답의 갯수가 출력됨.

 

 

HashMap 사용 코드

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        N = stoi(br.readLine());
        st = new StringTokenizer(br.readLine());
        HashMap< Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int temp = stoi(st.nextToken());
            Integer orDefault = map.getOrDefault(temp, 0);
            map.put(temp, orDefault+1);
        }

        int M = stoi(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int target = stoi(st.nextToken());
            System.out.print(map.getOrDefault(target,0) + " ");
        }
    }
}

 

 

이분탐색 lower bound / upper bound 사용 코드

 

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

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        N = stoi(br.readLine());
        card = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            card[i] = stoi(st.nextToken());
        }

        Arrays.sort(card);
        int M = stoi(br.readLine());
        int[] target = new int[M];
        st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < M; i++) {
            target[i] = stoi(st.nextToken());
        }

        for (int i : target) {
            int low = getLowerBound(i);
            int high = getUpperBound(i);
            System.out.print(high-low + " ");
        }
    }

    static int getLowerBound(int target){
        int left = 0;
        int right = N;

        while(left < right){
            int mid = (left + right)/2;
            if(card[mid] >= target){
                right = mid;
            } else {
                left = mid+1;
            }
        }

        return left;
    }

    static int getUpperBound(int target){
        int left = 0;
        int right = N;

        while(left < right){
            int mid = (left + right)/2;
            if(card[mid] <= target){
                left = mid+1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}