[BaekJoon]#10816 숫자카드 2

하하! 수 찾기 문제랑 비슷해서 바로 풀어버릴 줄 알았는데

💡 이분탐색의 목적: 특정 값에 대한 배열의 특정인덱스
중복원소는 정렬 후에 upperbound, lowerbound 이용

• 이 문제는 수 찾기 문제와 비슷하지만 고려해야할 부분이 있습니다.
• 바로 중복원소의 갯수를 알아내야 합니다. 종복되는 원소의 갯수를 세기 위해 어떤 방법이 제일 효율적일까요 ?
• 만약 중복되는 원소의 인덱스를 알고싶다면, 정렬 이후 중복원소의 시작 인덱스와 마지막 인덱스만 알고있다면, 해당 중복된 수의 총 갯수를 편리하게 구할 수 있습니다.

Lower Bound / Upper Bound

• Lower Bound : 하한(하계) 찾고자 하는 값 이상의 값이 처음으로 나타나는 인덱스를 의미합니다.

key = 4 라고 할 때, 이미지에서 처음으로 마주하는 key값 이상을 가지고 있는 값은 arr[3] 이므로 해당 값의 인덱스가 lower bound가 됩니다.

• Upper Bound : 상한(상계)는 찾고자 하는 값을 초과한 값을 처음 만나는 위치입니다.
  
• 위의 이미지에서, key값인 4보다 큰 처음 만나는 값은 arr[6]=6 입니다.
  따라서, upper bound의 값은 6이 됩니다.

---

• 만약, 위의 배열에서 key=5라면 upper bound = lower bound이 됩니다.

중복원소의 갯수?

• upper bound와 lower bound의 개념을 이용한다면 중복원소의 갯수를 구할 수 있습니다.
• 중복원소의 갯수 = 중복원소에 대한 길이= upper bound - lower bound

upper bound code

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;
    }

   

lower bound code

    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;
    }
}

10816 전체 코드

import java.util.StringTokenizer;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		
		Arrays.sort(arr);	
		int M = in.nextInt();
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < M; i++) {
			int key = in.nextInt();
 
			
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
		System.out.println(sb);
	}
 
 
	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;
	}
 
	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;
	}
	
}

참조블로그