[백준] 10816번 숫자카드 2문제 풀어보기 (이분탐색 활용)

1. 문제

www.acmicpc.net/problem/10816

문제는 위의 백준 링크에 들어가면 확인할 수 있다.

---

2. 풀이

이 문자는 이분탐색을 이용하여서 쉽게 해결할 수 있다. 먼저 해당 숫자가 몇번 나오는지를 count해야 하기 때문에 두가지 함수를 만들어줄 것이다.

1. lower_bound: 내가 찾는 숫자와 같은 수의 값을 가지고 있는 인덱스 중 가장 작은 인덱스를 return. 만약 없다면 -1 return
2. upper_bound: 내가 찾는 숫자와 같은 수의 값을 가지고 있는 인덱스 중 가장 큰 인덱스를 return. 없다면 -1을 return

즉 정렬을 해준뒤에 lower_bound와 upper_bound의 값을 얻으면 해당 숫자가 몇개가 있는지 쉽게 구할 수 있다. 예를 들어, lower_bound의 return 값이 3, upper_bound의 return 값이 5라면, 3,4,5번 index에 해당 숫자가 있는 것이기 때문에 총 (5-3+1)개가 있다고 할 수 있다. 

 

즉 우리는 (upper_bound의 return 값 - lower_bound의 return 값 +1) 만큼 해당 숫자가 존재한다고 할 수 있다. 

---

여기서 upper_bound와 lower_bound 함수는 이분탐색을 사용하여 쉽게 구현할 수 있다. 

 

먼저 lower_bound부터 살펴보겠다.

static int lower_bound(int num){ //같은 수 중에서 가장 작은 인덱스
        int n=a.length;
        int left=0;
        int right=n-1;
        int ans=-1; //못찾았을경우에는 -1
        while(left<=right){
            int mid=(left+right)/2;
            if (a[mid]==num){
                ans=mid;
                right=mid-1;
            }
            else if (a[mid]>num){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return ans;
    }

원하는 숫자를 찾은 뒤에는 right을 mid-1의 값으로 바꾸어주어 while문을 끝나게 만들어주어야 한다.

---

upper_bound 함수도 코드 한 줄만 수정하여 쉽게 구현할 수 있다. 

static int upper_bound(int num){ //같은 수 중에서 가장 큰 인덱스 
        int n=a.length;
        int left=0;
        int right=n-1;
        int ans=-1; //못찾았을경우에는 -1
        while(left<=right){
            int mid=(left+right)/2;
            if (a[mid]==num){
                ans=mid;
                left=mid+1;
            }
            else if (a[mid]>num){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return ans;
    }

upper_bound는 해당 숫자를 찾은 뒤에도 해당 숫자를 값으로 가지고 있는 최대 index를 찾아야 하므로 left의 값을 mid+1으로 수정시켜 계속 while문을 돌도록 해야 한다.

---

3. 코드

이것을 코드로 구현하면 아래와 같다.

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

public class Main{
    static int a[];
    static int lower_bound(int num){ //같은 수 중에서 가장 작은 인덱스
        int n=a.length;
        int left=0;
        int right=n-1;
        int ans=-1; //못찾았을경우에는 -1
        while(left<=right){
            int mid=(left+right)/2;
            if (a[mid]==num){
                ans=mid;
                right=mid-1;
            }
            else if (a[mid]>num){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return ans;
    }
    static int upper_bound(int num){ //같은 수 중에서 가장 큰 인덱스 
        int n=a.length;
        int left=0;
        int right=n-1;
        int ans=-1; //못찾았을경우에는 -1
        while(left<=right){
            int mid=(left+right)/2;
            if (a[mid]==num){
                ans=mid;
                left=mid+1;
            }
            else if (a[mid]>num){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return ans;
    }
    public static void main(String[] args) throws IOException{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        String[] line = br.readLine().split(" ");
         a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = Integer.valueOf(line[i]);
        }
        Arrays.sort(a);
        int m = Integer.valueOf(br.readLine());
        String[] s = br.readLine().split(" ");
        StringBuilder ans = new StringBuilder();
        for(int i=0; i<m; i++){
            int num=Integer.valueOf(s[i]);
            int low=lower_bound(num);
            int high=upper_bound(num);
            if (low==-1){
                //없다는 뜻이므로
                ans.append("0 ");
            }
            else{
                ans.append((high-low+1)+" ");
            }
        }
        System.out.println(ans);
    }
}