10816번

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

10816번: 숫자 카드 2

이 문제는 이분탐색 문제인데 lowerbound와 upperbound의 개념을 알아야 풀 수 있는 문제였다.. 그래서 애를 많이 먹었다.

나는 lowerbound와 upperbound를 말로는 이해하지 못했다.. 그림으로 이해했다.

 

먼저, lowerbound는 배열에서 범위 내의 원소들 중 찾으려는 값(key)보다 크거나 같은(key<=)첫번째 원소의 인덱스를 반환하는 것이다.

만약 원소가 없다면 end값을 리턴한다.

 

upperbound는 배열에서 처음으로 찾으려는 값(key)을 초과하는(key<) 원소의 인덱스를 반환한다. 만약 그런 원소가 없다면 end값을 리턴한다.

 

말로 하면 조금 헷갈리고 이해가 잘 안된다.

그래서 표를 그려봤다.

index	0	1	2(lower)	3	4	5(upper)
arr	0	3	5	5	5	6

위의 표에서 찾으려는 key값이 5일때, lowerbound는 2이고, upperbound는 5이다.

즉, lowerbound는 찾으려는 값중에서 제일 앞에 있는 값이고, upperbound는 중복되는 찾으려는 값들의 바로 다음 값이다.

 

그래서 이분탐색을 진행하면

먼저 lowerbound를 찾는 이분 탐색은 아래와 같다.

public static int lowerBound(int find, int start, int end){
    int mid;
    while (end-start>0){
        mid = (start+end)/2;
        if(arrN[mid]<find){
            start=mid+1;//찾으려는 값이 중간값보다 크면 시작지점을 옮긴다. 고려할 점은 시작지점은 찾으려는 값과 같아야한다. 
            //그래서 찾으려는 값이 크니까 +1을 해주는 것이다.
        }else end=mid;//찾으려는 값이 중간값보다 작거나 같으면(find<=arr[mid]) 끝지점을 중간값으로한다.
    }
    return end;
}

그 다음 upperbound는 아래와 같다.

public static int upperBound(int find, int start, int end){
    int mid;
    while (end-start>0){
        mid = (start+end)/2;

        if(arrN[mid]<=find){
            start=mid+1;//찾으려는 값보다 작거나 같으면 시작점을 옮긴다. 
        }else end=mid;//찾으려는 값보다 크면 끝점을 옮긴다. - 옮겨진 끝점이 찾으려는 값의 다음으로 큰 값이다.
    }
    return end;
}

그래서 이렇게 구한 두 범위의 값을 upperbound에서 lowerbound를 빼면 찾으려는 값의 갯수를 구할 수 있다.

 

정답 코드는 아래와 같다.

package backjoon;

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

public class b10816 {
    static int M;
    static int[] countArr;
    static int[] arrN;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Arrays.sort(arrN);

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] arrM = new int[M];
        countArr = new int[M];
        for(int i=0; i<M; i++){
            arrM[i]= Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<M; i++){
            int count = upperBound(arrM[i],0,N) - lowerBound(arrM[i],0,N);
            countArr[i]=count;
        }

        StringBuilder sb = new StringBuilder();
        for (int i : countArr) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }

    public static int lowerBound(int find, int start, int end){
        int mid;
        while (end-start>0){
            mid = (start+end)/2;
            if(arrN[mid]<find){
                start=mid+1;
            }else end=mid;
        }
        return end;
    }
    public static int upperBound(int find, int start, int end){
        int mid;
        while (end-start>0){
            mid = (start+end)/2;

            if(arrN[mid]<=find){
                start=mid+1;
            }else end=mid;
        }
        return end;
    }
}