8월 4일 99클럽 항해 14일

99클럽 항해 14일차

 

오늘의 문제는  숫자 카드2이다.

 

 

문제에서 주어진 두 값을 비교하여 값이 있으면 해당 값이 몇개가 있는지 수를 체크하는 문제가 되겠다.

        -> 배열로 상근이가 가진 숫자 카드를 받고 정렬한다.

        -> 이진탐색을 통한 uppperBound와 lowerBound를 구현한다.(해당값을 초과하는 인덱스 찾기 해당 값 과 같은 인덱스 찾기)

        -> 비교할 문자를 숫자로 변환하여 이진탐색을 하여 (해당 값을 초과하는 인덱스 - 해당 값과 같은 인덱스)를 계산한다.

        -> 이는 해당 값의 개수와 같으므로 값을 StringBuiler를 통하여 추가해준다.

순서로 문제를 해결하였다

 

    import java.io.*;
    import java.util.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            int[] arr1 = new int[n];
            HashMap<Integer, Integer> map = new HashMap<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr1[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr1);
    
            int m = Integer.parseInt(br.readLine());
            StringBuilder sb = new StringBuilder();
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            for (int i = 0; i < m; i++) {
                int a= Integer.parseInt(st1.nextToken());
                int b=upperBound(arr1,a)-lowerBound(arr1,a);
                sb.append(b).append(" ");
            }
            System.out.println(sb);
        }
    
        public static int lowerBound(int[] array, int value) {
            int low = 0;
            int high = array.length;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (value <= array[mid]) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    
        public static int upperBound(int[] array, int value) {
            int low = 0;
            int high = array.length;
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (value >= array[mid]) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return low;
        }
    }