[백준(Baekjoon)][자바(java)] 10816 : 숫자 카드 2 / 이분 탐색

 

www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

// 220512

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

public class Main {

	public static int lower_bound(int n, int a[], int k) {
		int start = 0, end = n - 1, mid = 0;
		while (start <= end) {
			mid = (start + end) / 2;
			if (a[mid] >= k)		end = mid - 1;
			else			start = mid + 1;
		}
		return start;
	}
	
	public static int upper_bound(int n, int a[], int k) {
		int start = 0, end = n - 1, mid = 0;
		while (start <= end) {
			mid = (start + end) / 2;
			if (a[mid] > k)		end = mid - 1; 
			else			start = mid + 1;
		}
		return start;
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int a[] = new int[n], i;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (i = 0; i < n; ++i) 
			a[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(a);
		
		int m = Integer.parseInt(br.readLine()), num;
		st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();		
		for (i = 0; i < m; ++i) {
			num = Integer.parseInt(st.nextToken());
			sb.append((upper_bound(n, a, num) - lower_bound(n, a, num)) + " ");
		}
		br.close();
		
		System.out.println(sb.toString());
	}
}

 

예) 

10  ( int n )
6 3 2 10 10 10 -10 -10 7 3  ( int a[] )
8  ( int m )
10 9 -5 2 3 4 5 -10  ( int k (StringTokenizer) )

 

배열 a에 n개의 값을 입력받은 후 오름차순 정렬

 

(m개의 값을 차례대로 보면서) up(상한값) - lo(하한값) = 배열 a에서 k가 들어있는 개수