https://www.acmicpc.net/problem/10816
Map 이용
import java.util.*;
import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<Integer,Integer> hashmap = new HashMap();
int n = Integer.valueOf(br.readLine());
String[] input1 = br.readLine().split(" ");
int[] num1 = new int[n];
int m = Integer.valueOf(br.readLine());
String[] input2 = br.readLine().split(" ");
for(int i=0;i<n;i++){
hashmap.put(Integer.valueOf(input1[i]),hashmap.getOrDefault(Integer.valueOf(input1[i]),0)+1);
}
StringBuilder sb = new StringBuilder();
for(int i=0;i<m;i++){
int num=Integer.valueOf(input2[i]);
sb.append(hashmap.getOrDefault(Integer.valueOf(num),0));
sb.append(" ");
}
System.out.println(sb.toString());
}
}
이분탐색 이용
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;
class Main
{
static int findLowerBoundIndex(int[] arr, int x) {
// x 이상의 값이 처음으로 나타나는 위치
int lowerBoundIndex = arr.length;
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (arr[m] < x) l = m + 1;
else {
r = m - 1;
lowerBoundIndex = m;
}
}
return lowerBoundIndex;
}
static int findUpperBoundIndex(int[] arr, int x) {
// x 초과의 값이 처음으로 나타나는 위치
int upperBoundIndex = arr.length;
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (arr[m] <= x) l = m + 1;
else {
r = m - 1;
upperBoundIndex = m;
}
}
return upperBoundIndex;
}
public static void main (String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] cards = new int[N];
for (int i = 0; i < N; i++)
cards[i] = sc.nextInt();
Arrays.sort(cards);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int M = sc.nextInt();
while (M-- > 0) {
int x = sc.nextInt();
int lowerBoundIndex = findLowerBoundIndex(cards, x);
int upperBoundIndex = findUpperBoundIndex(cards, x);
bw.write(upperBoundIndex - lowerBoundIndex + " ");
}
bw.write("\n");
bw.flush();
}
}
'Problem Solving > 이진 탐색' 카테고리의 다른 글
BOJ1654 랜선 자르기 (매개변수 탐색) (0) | 2024.02.27 |
---|---|
BOJ2805 나무자르기 (매개변수탐색) (1) | 2024.02.27 |
BOJ2470 두 용액 (0) | 2024.02.14 |
BOJ14425 문자열 집합 (0) | 2024.02.13 |
이분 탐색 개념 (0) | 2024.02.13 |