[07.28] 백준 10816번

문제 10816번

이분탐색 (upper, lower)

• 전에 10815번 숫자카드 문제에서 인덱스 값의 유무를 판단하는 이분탐색을 사용 했었다. 10815번
• 이번에는 해당 값의 개수를 구하는 문제이기 때문에 upper, lower 탐색법을 설명하고자 한다.
• 아래는 upper와 lower 탐색 코드이다.
  • upper와 lower 함수가 똑같이 보일 것이다. 그러나 자세히 보면 while문 안에 있는 if의 조건이 미만과 이하로 구분 된다.
    
  • 위 사진처럼 주어진 배열에서 key가 4인 값을 찾고자 할 때, upper 에서는 arr[mid]가 4여도 else로 빠지기 때문에 결국 lo의 값이 6 hi 값이 5에서 반복문을 탈출하게 되어 6이 반환될 것이다. 그러나 lower 함수에서는 가장 앞 값인 3이 반환될 것이다.

private static int upperBound(int[] arr, int key){
        int lo = 0;
        int hi = arr.length;
        while(lo < hi){
            int mid = (lo + hi)/2;
            if(key < arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }
private static int lowerBound(int[] arr, int key){
        int lo = 0;
        int hi = arr.length;
        while(lo<hi){
            int mid = (lo+hi)/2;
            if(key <= arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }

• 이러한 특징 때문에 lower과 upper는 해당 값의 개수를 구할 때 주로 함께 사용된다.

소스코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class boj10816 {
    private static int upperBound(int[] arr, int key){
        int lo = 0;
        int hi = arr.length;
        while(lo < hi){
            int mid = (lo + hi)/2;
            if(key < arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }
    private static int lowerBound(int[] arr, int key){
        int lo = 0;
        int hi = arr.length;
        while(lo<hi){
            int mid = (lo+hi)/2;
            if(key <= arr[mid]){
                hi = mid;
            }else{
                lo = mid +1;
            }
        }
        return lo;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[] firstarr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            firstarr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(firstarr);
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int input = Integer.parseInt(st.nextToken());
            sb.append( upperBound(firstarr,input) - lowerBound(firstarr,input)+ " ");
        }
        System.out.println(sb);
    }
 }

문제 접근

1. 상근이가 가진 카드를 배열로 받는다.
2. 문제에서 주어진 상근이의 카드 개수의 제한이 크기 때문에 시간복잡도를 줄이기 위해서 이분탐색을 방법을 선택하고, 배열을 오름차순으로 정렬한다.
3. 다음은 해당 카드를 몇 장 가지고 있는지를 출력해야 하기 때문에 이분탐색 방법 중에 upper, lowerbound 탐색을 선택 했다.
4. lower의 경우 가장 앞 인덱스를 반환하고, upper의 경우 가장 뒤 인덱스 +1을 반환하기 때문에 upper 값에서 lower 값을 빼주면 해당 카드의 개수가 출력된다.

문제 핵심

• N의 한계가 큰 문제임으로 시간복잡도를 줄일 수 있는 탐색법을 찾기!